Apa iku teknik sliding-window?

Question

Accepted Answer

Teknik **sliding-window** ngeduweni jangkauan kontinu (window) ing saindhenging array utawa string lan nggeser saengga ora kudu ngrekomputasi saka nol, nglěsaaken akeh masalah subarray/substring ing **O(n)**.

## Ide pokok

Pawaké window kanthi nggeser pinggir kuwa; cilakaké kanthi nggeser pinggir kiwa nalika pembatasan dilanggar. Ngalehake komputasi sadurunge tinimbang ngscan ulang.

## Conto: maksimal jumlah saka window ukuran 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)
```

## Kerumitan

- **Wektu:** O(n) — saben elemen mlebu lan ninggal window salung wae.
- **Spasi:** O(1) kanggo fixed window, O(k) nalika nglacak isi.

## Kapan nganggo / jebakan

Gunakake kanggo masalah "subarray paling dawa/paling cekak/maksimal kanthi properti X". Kanggo window **variabel**, majunge pointer kiwa kanggo mulihake pembatasan. Ati-atèn kesalahan off-by-one nalika nambah/nglangkahi unsur wates.

## Mengapa iku penting

Sliding window ngilangake pakaryan sing diulang, ngobah rekomputasi O(n·k) dadi satuwan lintasan.

Iku pola standar kanggo masalah substring lan subarray sing mula ing wawancara.

Wawasan — ngalehake asil sadurunge tinimbang ngrekomputasi — umum kanggo streaming lan data real-time.