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

Когда интересует непрерывный участок

Скользящее окно применяют, когда задача работает с последовательными элементами массива: например, нужно найти лучший подмассив фиксированной длины. Вместо того чтобы заново считать результат для каждого диапазона, можно обновлять уже известное значение при сдвиге окна на одну позицию.

Пусть нужно найти максимальную сумму любых трёх соседних элементов. Сначала посчитаем сумму первого окна.

int windowSize = 3;
int windowSum = 0;

for (int i = 0; i < windowSize; i++) {
    windowSum += numbers[i];
}

int maxSum = windowSum;

Сдвигаем, а не пересчитываем

При переходе к следующему окну почти все элементы остаются теми же. Из суммы достаточно вычесть элемент, который вышел слева, и прибавить новый элемент, вошедший справа.

for (int right = windowSize; right < numbers.length; right++) {
    int left = right - windowSize;

    windowSum -= numbers[left];
    windowSum += numbers[right];
    maxSum = Math.max(maxSum, windowSum);
}

После первоначального подсчёта каждый сдвиг требует постоянного числа операций. Поэтому весь алгоритм выполняется за O(n), тогда как полный пересчёт суммы каждого окна привёл бы к лишней повторной работе.

Что именно хранит окно

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