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

От перебора к короткому примеру

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

Инвариант

После обновления total равен сумме последних k элементов, а best — максимальной сумме среди уже рассмотренных окон. Фиксированное окно допускает отрицательные значения: решение не сжимает границу по условию суммы.

1. a = [2, -1, 3, 4], k = 2. Первое окно [2, -1] даёт 1; best = 1.
2. Уходит 2, приходит 3: total = 1 − 2 + 3 = 2. Затем уходит −1, приходит 4: total = 2 − (−1) + 4 = 7.
3. Ответ 7. Если k < 1 или k > n, окна нет: C++ возвращает nullopt, Python — None.

Код на C++ и Python

Обе версии реализуют один контракт. Выберите язык кнопками над кодом; примеры проверяются на маленьких входах и граничных случаях.

#include <algorithm>
#include <optional>
#include <vector>

std::optional<long long> max_window_sum(const std::vector<int>& a, int k) {
    int n = static_cast<int>(a.size());
    if (k < 1 || k > n) return std::nullopt;
    long long total = 0;
    for (int i = 0; i < k; ++i) total += a[i];
    long long best = total;
    for (int right = k; right < n; ++right) {
        total += static_cast<long long>(a[right]) - a[right - k];
        best = std::max(best, total);
    }
    return best;
}

def max_window_sum(a, k):
    n = len(a)
    if k < 1 or k > n:
        return None
    total = 0
    for i in range(k):
        total += a[i]
    best = total
    for right in range(k, n):
        total += a[right] - a[right - k]
        best = max(best, total)
    return best

Проверьте контракт

• [2, -1, 3, 4], k = 2 → 7
• [-5, -2], k = 1 → -2, не 0
• [1, 2], k = 2 → 3
• [] или k = 0 или k > n → окна нет

Сложность и ограничения метода

• Первую сумму считаем за O(k), остальные обновляем за O(1): всего O(n) времени, O(1) дополнительной памяти при арифметике постоянной стоимости. Пример не создаёт срезы Python, которые добавили бы O(k) работы.
• Переменное окно требует другого инварианта: расширяем right и при нарушении условия двигаем left. Движения границ линейны, но стоимость состояния надо учитывать отдельно: частоты в хеш-таблице дают ожидаемую, не безусловную, оценку.
• Сжатие по превышению суммы работает для подходящих условий на неотрицательных числах. Контрпример с отрицательными: [4, -3], порог 2. Если удалить 4 сразу после превышения порога, потеряется допустимое окно суммы 1 длины 2.
• Непрерывность обязательна: подпоследовательность с пропусками не является окном. C++: размер помещается в int, суммы — в long long; преобразование перед вычитанием предотвращает переполнение int. Python: большие целые увеличивают стоимость арифметики.

Следующий шаг

• Полный урок: окно фиксированной длины
• Переменное окно: подстрока без повторов
• Задачи и самостоятельная практика