Sliding window adalah cara menghitung sesuatu dari sekelompok angka yang bersebelahan di array, misalnya jumlah 3 angka berturut-turut, lalu menggeser kelompok itu satu langkah demi satu langkah. Kelompok itu disebut jendela (window), dan banyaknya angka di dalamnya disebut k. Mirip jendela kereta: tiap kali kereta maju, satu pemandangan masuk dari kanan dan satu keluar di kiri.
🧪 Tebakan cepat: jendela
[2, 1, 5]jumlahnya 8. Digeser satu langkah jadi[1, 5, 1]. Perlu menjumlah tiga angka lagi dari nol, atau cukup dua hitungan? Tebak dulu, jawabannya ada di bagian "Geser, jangan hitung ulang".
Geser, jangan hitung ulang
Soalnya: cari jumlah terbesar dari k = 3 angka yang bersebelahan di [2, 1, 5, 1, 3, 2, 8, 4].
| Langkah | Jendela | Hitungannya | Jumlah | Terbesar sejauh ini |
|---|---|---|---|---|
| 1 | 2, 1, 5 | 2 + 1 + 5 | 8 | 8 |
| 2 | 1, 5, 1 | 8 - 2 + 1 | 7 | 8 |
| 3 | 5, 1, 3 | 7 - 1 + 3 | 9 | 9 |
| 4 | 1, 3, 2 | 9 - 5 + 2 | 6 | 9 |
| 5 | 3, 2, 8 | 6 - 1 + 8 | 13 | 13 |
| 6 | 2, 8, 4 | 13 - 3 + 4 | 14 | 14 |
Cuma jendela pertama yang dijumlah lengkap. Sesudahnya, tiap geser cukup dua hitungan: kurangi angka yang keluar di kiri, tambah angka yang masuk di kanan. Itu jawaban tebakan tadi. Kalau array-nya cuma [2, 1, 5, 1, 3, 2], jendelanya berhenti di langkah 4, dan jawabannya 9.
function maxSumSubarray(arr, k) {
let jumlah = 0;
for (let i = 0; i < k; i++) {
jumlah += arr[i];
}
let maksimum = jumlah;
for (let i = k; i < arr.length; i++) {
jumlah += arr[i] - arr[i - k];
if (jumlah > maksimum) {
maksimum = jumlah;
}
}
return maksimum;
}
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2, 8, 4], 3)); // 14
- Loop pertama menjumlah
kangka pertama. Itu jendela pertama: 2 + 1 + 5 = 8. maksimummulai dari jumlah jendela pertama. Dia juara sementara.- Loop kedua mulai dari
i = kdan menggeser jendela satu langkah tiap putaran.arr[i]adalah angka yang masuk dari kanan,arr[i - k]adalah angka yang keluar dari kiri. jumlah += arr[i] - arr[i - k]artinya: tambah yang masuk, kurangi yang keluar.- Kalau jumlah yang baru lebih besar, dia jadi
maksimum. Setelah loop selesai,maksimumdi-return.
Dua loop itu terpisah, bukan bersarang (loop di dalam loop). Dan keduanya memakai k dari parameter, jadi function-nya benar untuk lebar jendela berapa pun.
Kenapa lebih cepat
Cara biasa menjumlah ulang k angka di setiap posisi jendela, jadi kerjanya kira-kira n × k: O(n × k). Kalau k hampir sebesar n, itu mendekati O(n²), seperti loop bersarang.
Sliding window cuma butuh O(n). Artinya: datanya dua kali lipat, waktunya kira-kira dua kali lipat juga. Sebabnya, tiap angka paling banyak diproses dua kali: sekali waktu masuk jendela, sekali waktu keluar. Di Lab dengan 8 angka dan k = 3, cara geser butuh 13 operasi, cara hitung ulang 18. Makin besar k, makin jauh bedanya.
Pakai sliding window kalau soalnya tentang angka atau huruf yang bersebelahan: "jumlah 5 hari berturut-turut", "rata-rata 7 data terakhir". Kalau boleh memilih angka dari mana saja, itu bukan soal jendela.
⚠️ Jebakan yang sering ketemu
- Angka
3ditulis langsung. Loopi < 3cuma benar kalaukkebetulan 3. Pakaikdi kedua loop. - Jendela pertama lupa dijumlah. Loop geser mulai dari
i = k, jadikangka pertama harus sudah ada dijumlahsebelumnya. - Yang dikurangi salah. Angka yang keluar ada di
arr[i - k], bukanarr[i - 1]. maksimummulai dari 0. Kalau semua angkanya negatif, jawabannya jadi 0, padahal gak ada jendela yang jumlahnya 0. Mulai dari jumlah jendela pertama.
💡 Jendela yang lebarnya berubah. Ada juga soal seperti "jendela terpendek yang jumlahnya minimal 7". Di situ lebarnya gak tetap: ujung kanan maju untuk menambah angka, lalu ujung kiri maju untuk membuang angka selama syaratnya masih terpenuhi. Idenya sama: tiap angka masuk sekali dan keluar sekali.
TL;DR: Sliding window menghitung kelompok k angka yang bersebelahan, lalu menggesernya satu langkah. Jumlahkan jendela pertama sekali, lalu tiap geser cukup jumlah += arr[i] - arr[i - k]: tambah yang masuk, kurangi yang keluar. Simpan yang terbesar di maksimum yang mulai dari jendela pertama. Hasilnya O(n), bukan O(n × k), karena tiap angka diproses paling banyak dua kali.
