Apa itu teknik sliding-window?

Question

Accepted Answer

Teknik **sliding-window** mempertahankan rentang yang berdekatan (jendela) pada array atau string dan meluncurkannya daripada menghitung ulang dari awal, menyelesaikan banyak masalah subarray/substring dalam **O(n)**.

## Idenya

Perluas jendela dengan memindahkan tepi kanan; kecilkan dengan memindahkan tepi kiri ketika constraint dilanggar. Gunakan kembali komputasi sebelumnya daripada memindai ulang.

## Contoh: max sum dari jendela berukuran 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)
```

## Kompleksitas

- **Waktu:** O(n) — setiap elemen masuk dan keluar dari jendela sekali.
- **Ruang:** O(1) untuk jendela tetap, O(k) ketika melacak isi.

## Kapan menggunakan / jebakan

Gunakan untuk masalah "subarray terpanjang/terpendek/max dengan property X". Untuk jendela **variabel**, majukan pointer kiri untuk memulihkan constraint. Waspadai kesalahan off-by-one saat menambah/menghapus elemen boundary.

## Mengapa ini penting

Sliding window menghilangkan pekerjaan redundan, mengubah rekomputasi O(n·k) menjadi satu pass.

Ini adalah pola standar untuk masalah substring dan subarray yang muncul terus-menerus dalam interview.

Wawasan — gunakan kembali hasil sebelumnya daripada menghitung ulang — generalisasi ke streaming dan data real-time.