Menene dabaran gudar fuska?

Question

Accepted Answer

Dabaran **gudar fuska** yana kiyaye iko mai jajere (fuska) akan ƙarshe ko kamus sannan yana yin gudu a maimakon sake ƙididdige daga gida, muna warware matsalolin subarray/substring da yawa a cikin **O(n)**.

## Tunani

Faɗaɗa fuska ta hanyar motsa gida na dama; rage ta ta hanyar motsa gida na hagu lokacin da aka karya takaitawa. Sake amfani da lissafin baje daga jiya a maimakon sake dubawa.

## Misali: matsakaicin jimla na kowane fuska na girman k

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Hadaddiyar lissafi

- **Lokaci:** O(n) — kowane kashi yana shiga da fita daga fuska sau ɗaya.
- **Ƙauri:** O(1) ga fuska da aka kayyade, O(k) lokacin kiyaye abubuwa.

## Yaushe ake amfani da shi / hadaddiyar ajiya

Amfani don "mafi girma/mafi gida/matsakaicin subarray tare da kadarorin X" matsaloli. Don **babbayya** fuska, kara gida na hagu don dawo da takaitawa. Kula da kuskure na gida-gida lokacin ƙara/cire abubuwan gida.

## Me yasa ya cancanta

Gudar fuska yana kawar da aikin da baba, yana juyar da O(n·k) sake ƙididdige zuwa ƙarar daya.

Ita ce tashin jima niyyata don matsalolin kamus da subarray da aka nuna a jiya a cikin shawarwari.

Tunani — sake amfani da sakamakon jiya a maimakon sake ƙididdige — yana tattauna zuwa stratum da bayani na aiki.