Скользящее окно

Скользящее окно поддерживает подотрезок (окно) и пересчитывает его характеристику инкрементально при сдвиге, вместо повторного прохода. Подходит для задач о подмассивах и подстроках.

Сложность: время O(n); память: O(1) или O(размер алфавита). Примеры: максимальная сумма окна длины k, самая длинная подстрока без повторов.

def max_sum_window(a, k):
    window = sum(a[:k])
    best = window
    for i in range(k, len(a)):
        window += a[i] - a[i - k]   # сдвиг окна O(1)
        best = max(best, window)
    return best

print(max_sum_window([1, 4, 2, 10, 2, 3], 3))  # 16