La technique de la fenêtre glissante maintient une plage contiguë (fenêtre) sur un tableau ou une chaîne de caractères et la fait glisser au lieu de recalculer à partir de zéro, résolvant de nombreux problèmes de sous-tableau/sous-chaîne en O(n).
L'idée
Élargissez la fenêtre en déplaçant le bord droit ; rétrécissez-la en déplaçant le bord gauche quand une contrainte est violée. Réutilisez le calcul précédent au lieu de rescanner.
Exemple : somme maximale de toute fenêtre de taille k
():
window = (arr[:k])
best = window
i (k, (arr)):
window += arr[i] - arr[i - k]
best = (best, window)
best
max_window_sum([, , , , , ], )
