Окно фиксированного размера

Рассмотрим задачу: среди всех непрерывных фрагментов длины k найти фрагмент с максимальной суммой. Для [1, 4, 2, 10] и k = 2 суммы равны 5, 6 и 12, поэтому ответ — 12.

Какие фрагменты участвуют в поиске максимальной суммы

Выбирается именно непрерывный диапазон из ровно k элементов. Его начало может быть в любой позиции от 0 до n - k. Нужно вернуть максимальную сумму, не создавая копию каждого диапазона.

Сколько раз прямой подход суммирует одно значение

Для каждого возможного начала можно заново сложить следующие k элементов. Окон n - k + 1, каждое требует k сложений, поэтому время равно O((n - k + 1) · k), в худшем случае O(n²). Дополнительная память — O(1).

Почему соседние окна повторяют почти всю работу

Соседние окна почти совпадают. Например, [1, 4] и [4, 2] оба содержат 4, но полный перебор суммирует его заново. При каждом сдвиге повторно обрабатываются k - 1 элементов, хотя изменились только две границы.

Один элемент уходит, другой приходит

Пусть известна сумма окна [left, right). После сдвига на одну позицию элемент values[left] уходит, а values[right] приходит. Новую сумму можно получить двумя операциями:

new_sum = old_sum - leaving + entering.

Так каждое следующее окно обрабатывается за O(1).

Что означают window и best

После обработки правой границы right:

• window равен сумме ровно k элементов в диапазоне [right - k + 1, right];
• best равен максимальной сумме среди всех окон длины k, которые заканчиваются не правее right.

Перед первым сдвигом эти свойства задаются суммой диапазона [0, k).

Строим первое окно и сдвигаем границы

1. Проверить, что 1 <= k <= n.
2. Один раз вычислить сумму первых k элементов и записать её в window и best.
3. Для каждого right от k до n - 1 добавить values[right].
4. Вычесть уходящий элемент values[right - k].
5. Обновить best максимумом из старого значения и window.
6. Вернуть best.

Максимальная сумма с проверкой длины окна

C++17

#include <algorithm>
#include <cassert>
#include <iostream>
#include <stdexcept>
#include <vector>

long long maxWindowSum(const std::vector<int>& values, std::size_t k) {
    if (k == 0 || k > values.size()) {
        throw std::invalid_argument("k must be between 1 and values.size()");
    }

    long long window = 0;
    for (std::size_t index = 0; index < k; ++index) {
        window += static_cast<long long>(values[index]);
    }

    long long best = window;
    for (std::size_t right = k; right < values.size(); ++right) {
        window += static_cast<long long>(values[right]);
        window -= static_cast<long long>(values[right - k]);
        best = std::max(best, window);
    }

    return best;
}

int main() {
    assert(maxWindowSum({1, 4, 2, 10}, 2) == 12);
    assert(maxWindowSum({-8, -5, -6}, 2) == -11);
    assert(maxWindowSum({7}, 1) == 7);
    std::cout << "OK\n";
}

Python 3

def max_window_sum(values: list[int], k: int) -> int:
    if k < 1 or k > len(values):
        raise ValueError("k must be between 1 and len(values)")

    window = sum(values[:k])
    best = window

    for right in range(k, len(values)):
        window += values[right]
        window -= values[right - k]
        best = max(best, window)

    return best


assert max_window_sum([1, 4, 2, 10], 2) == 12
assert max_window_sum([-8, -5, -6], 2) == -11
assert max_window_sum([7], 1) == 7
print("OK")

Почему все окна обрабатываются за линейное время

Первое окно требует O(k), остальные n - k сдвигов — по O(1). Итого O(n) времени и O(1) дополнительной памяти.

В C++ сумма хранится в long long; предполагается, что сумма любых k входных int помещается в этот тип. Функции явно отклоняют k = 0 и k > n.

Нулевая длина, весь массив и отрицательные суммы

• k = 1: ответ равен максимальному элементу.
• k = n: существует ровно одно окно — весь массив.
• Все числа отрицательные: best нельзя начинать с нуля.
• Пустой массив не допускает ни одного корректного положительного k.
• k = 0 или k > n: код сообщает об ошибке вместо обращения за границы.
• Большие значения: в C++ расширение до long long выполняется перед сложением и вычитанием.

Проверяем единственное окно и отрицательный максимум

• [1, 4, 2, 10], k = 2 → 12.
• [-8, -5, -6], k = 2 → -11, окно [-5, -6].
• [7], k = 1 → 7.
• [3, -1, 4], k = 3 → 6.
• Любой массив, k = 0 → ошибка входных данных.

Сигнал фиксированной длины и локального агрегата

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

Когда вычитания уходящего элемента недостаточно

Эта простая формула подходит, когда вклад уходящего элемента можно убрать за O(1). Например, для максимума окна одного вычитания недостаточно: если ушёл прежний максимум, нужно найти следующий. Для такой задачи обычно нужна монотонная очередь. Если длина диапазона меняется по условию, требуется окно переменного размера и отдельное доказательство сжатия.

Почему best нельзя начинать с нуля

Вопрос. Почему best = 0 ломает решение на [-8, -5, -6] при k = 2?

Ответ. Допустимые суммы равны -13 и -11; максимум среди них — -11. Ноль не является суммой ни одного окна, но алгоритм ошибочно вернул бы его. Поэтому best инициализируется суммой первого реального окна.

Как найти индекс уходящего элемента

Вопрос. Почему при добавлении элемента с индексом right уходит именно индекс right - k?

Ответ. Старое окно равно [right - k, right). После добавления right оно временно содержит k + 1 элемент; удаление его левой границы right - k оставляет новое окно [right - k + 1, right + 1) длины k.

Переходим от суммы к среднему

Задание. Найдите максимальное среднее окна длины 4 в массиве [1, 12, -5, -6, 50, 3].

Подсказки. Знаменатель у всех окон одинаков, поэтому достаточно максимизировать сумму тем же алгоритмом, а разделить на k только один раз в конце. Суммы последовательных окон: 2, затем 51, затем 42.

Проверка. Максимальная сумма 51, поэтому ответ 51 / 4 = 12.75.

Самостоятельная задача о гласных в окне

Задача 1

Для строки из строчных латинских букв и целого k найдите максимальное число гласных среди всех подстрок длины ровно k. Явно определите поведение при недопустимом k и приведите тест со строкой без гласных.

Сдвиг сохраняет работу перекрывающихся окон

Фиксированное окно превращает повторное суммирование перекрывающихся диапазонов в один проход: точно учитываем один входящий и один уходящий элемент и постоянно сохраняем сумму текущего окна.