Техника sliding-window поддерживает смежный диапазон (окно) над массивом или строкой и скользит по нему вместо пересчета с нуля, решая множество задач с подмассивами/подстроками за O(n).
Идея
Расширьте окно, переместив правую границу; сожмите его, переместив левую границу, когда нарушается ограничение. Повторно используйте предыдущее вычисление вместо повторного сканирования.
Пример: максимальная сумма любого окна размером k
():
window = (arr[:k])
best = window
i (k, (arr)):
window += arr[i] - arr[i - k]
best = (best, window)
best
max_window_sum([, , , , , ], )
