Скользящее окно (фиксированный размер)

O(n)

Держать окно ровно из k элементов и сдвигать его на шаг за раз: добавлять входящий элемент, убирать выходящий и обновлять текущий ответ без пересчёта всего окна.

Сигналы

непрерывный подмассив/подстрока заданной длины kкаждое окно размера kскользящее среднее или скользящая суммамин/макс/количество/сумма по каждому фиксированному отрезку

Шаблон

function windowStat(arr, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) windowSum += arr[i];
    let best = windowSum;
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

Похоже, но не то

Скользящее окно переменного размера: Фиксированное окно на всём проходе имеет размер ровно k и никогда не растёт и не сужается. У переменного окна нет фиксированного k: оно само растёт и сужается в зависимости от того, выполняется ли условие.
Префиксные суммы: Префиксные суммы считаются один раз заранее, чтобы потом за O(1) отвечать на ЛЮБОЙ произвольный диапазон. Фиксированное окно катит один отрезок размера k вперёд и отвечает только про этот один движущийся отрезок.

n до 1e5..1e6 -> O(n): каждый элемент входит в окно и выходит из него ровно один раз, поэтому сдвиг это один линейный проход, а не O(nk) с пересчётом.

Изучить этот паттерн