Maximum Sum Subarray of Size K

Q: Что такое скользящее окно фиксированного размера?

Это диапазон ровно из k соседних элементов, который перемещается по массиву шаг за шагом. Вместо того чтобы каждый раз заново вычислять диапазон, вы обновляете текущее значение: добавляете элемент, который входит справа, и удаляете тот, который выходит слева. Это сокращает объём работы с O(n·k) до O(n) .

Q: Чем это отличается от задачи о максимальном подмассиве?

Здесь длина фиксирована и равна k , поэтому каждый кандидат — это окно, а скользящая сумма охватывает их все. В задаче о максимальном подмассиве длина не фиксирована, и нужен алгоритм Кадане, который для каждого элемента решает, расширить ли текущий отрезок или начать новый. У окна фиксированной длины такого выбора нет.

Q: Могут ли префиксные суммы тоже решить эту задачу?

Да. Постройте prefix[i] как сумму первых i элементов, и сумма окна, начинающегося с s , равна prefix[s+k] - prefix[s] . Это тоже занимает время O(n) , но требует хранения n+1 сумм. Скользящее окно вычисляет те же суммы с помощью двух переменных.

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

+10

Дан массив целых чисел nums и длина окна k. Рассмотрите каждый непрерывный участок ровно из k соседних элементов и верните наибольшую сумму среди них. Значения могут быть отрицательными, поэтому и ответ может быть отрицательным.

Функция

maxSumSubarray(nums: integer-array, k: integer) → integer

numsinteger-array: массив целых чисел
kinteger: сколько соседних элементов содержит каждое окно
Возвращаетinteger: наибольшая сумма любых k последовательных элементов

Ограничения

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Примеры

Ввод: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Вывод: 10
Пояснение: Сумма пяти окон длиной 3 равна 6, 9, 8, 10 и 4. Наибольшая сумма — 7 + (-2) + 5 = 10.

Ввод: nums = [-3, -8, -1, -6]k = 2
Вывод: -7
Пояснение: Все значения отрицательные, поэтому и сумма в каждом окне отрицательная: -11, -9 и -7. Наибольшая из них — -1 + (-6) = -7.

Ввод: nums = [5, -2, 4]k = 3
Вывод: 7
Пояснение: Когда k равен длине массива, существует одно окно — весь массив, и 5 + (-2) + 4 = 7.

+15 скрытых тестов при отправке

Дополнительный вопрос

Можешь также вернуть, где начинается лучшее окно, выбирая самое левое, если несколько окон имеют одинаковый результат?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Сложите все окна

Верно, но не успевает на самых больших тестах

Идея

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

Для [4, -1, 3, 7, -2, 5, 1] и k = 3 получаются суммы 6, 9, 8, 10, 4, и ответ — 10. В качестве максимума возьми сумму первого окна или наименьшее целое число — никогда не начинай с 0: если все значения отрицательные, 0 будет больше суммы любого настоящего окна.

Вычислительная стоимость составляет (n-k+1) × k сложений. Она достигает максимума, когда k примерно равен половине n: при n = 10^4 и k = 5000 это 5001 × 5000, то есть около 2.5 × 10^7 сложений, и почти все они повторяют вычисления, уже выполненные для предыдущего окна.

Алгоритм

Установи best в минимально возможное значение.
Для каждого значения start от 0 до n-k установи total = 0.
Добавляй значения от nums[start] до nums[start+k-1] к total.
Если total больше best, сохрани его.
Верни best.

def maxSumSubarray(nums, k):
    n = len(nums)
    best = None
    for start in range(n - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

Сдвиньте окно фиксированного размера

Идея

Сравним окно, начинающееся с индекса 0, с окном, начинающимся с индекса 1. В [4, -1, 3, 7, -2, 5, 1] при k = 3 это 4 + (-1) + 3 = 6 и (-1) + 3 + 7 = 9. В обоих есть -1 и 3. Вторая сумма равна первой плюс значение, которое добавилось, 7, минус значение, которое выбыло, 4: 6 + 7 - 4 = 9.

Это верно для каждого шага. Когда правый край окна перемещается к индексу i, элемент с индексом i добавляется, а элемент с индексом i-k выбывает. Поэтому сначала один раз вычисли сумму первого окна, а затем обновляй её, выполняя одно сложение и одно вычитание на каждом шаге. Получаются суммы 6, 9, 8, 10, 4 — такие же, как при полном переборе, — и ты сохраняешь наибольшую.

Каждый элемент добавляется один раз и выбывает не более одного раза, поэтому время работы составляет O(n). Ты хранишь два числа: сумму текущего окна и наибольшую сумму, поэтому дополнительная память составляет O(1). Здесь ни одна сумма не превышает 10^4 × 10^4 = 10^8, поэтому достаточно 32-битного целого числа.

Алгоритм

Сложи nums[0] до nums[k-1] включительно в window.
Присвой best = window.
Для каждого i от k до n-1 добавь nums[i] и вычти nums[i-k].
После каждого шага присваивай best большее из значений best и window.
Верни best.

def maxSumSubarray(nums, k):
    # Sum of the first window, nums[0..k-1].
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        # Slide one step right: nums[i] enters, nums[i-k] leaves.
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Ловушки и крайние случаи

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

Начальное значение best равно 0. Для [-3, -8, -1, -6] и k = 2 правильный ответ — -7, но значение best, равное 0, никогда не будет превзойдено, и вернётся в качестве ответа.
Вычитание неправильного элемента. Когда добавляется nums[i], удаляется nums[i-k]. Если использовать nums[i-k+1] или nums[i-k-1], получатся окна неправильной длины.
Слишком ранняя остановка полного перебора. Последнее окно начинается с n-k, поэтому этот элемент нужно включить в цикл. При k = n это единственное окно, а ошибка на единицу приведёт к тому, что цикл не проверит ни одного окна и вернёт начальное значение best.
Сравнение только после цикла. Лучшим может оказаться первое окно, поэтому сравните с ним сумму тоже или присвойте её переменной best при инициализации.
Забывают, что в R и Lua отсчёт начинается с 1. Первое окно — это nums[1..k], а элемент, который удаляется при добавлении nums[i], — всё так же nums[i-k].

Частые вопросы4

Что такое скользящее окно фиксированного размера?

Это диапазон ровно из k соседних элементов, который перемещается по массиву шаг за шагом. Вместо того чтобы каждый раз заново вычислять диапазон, вы обновляете текущее значение: добавляете элемент, который входит справа, и удаляете тот, который выходит слева. Это сокращает объём работы с O(n·k) до O(n).

Какова временная сложность алгоритма поиска подмассива длины k с максимальной суммой?

При использовании скользящего окна временная сложность составляет O(n), а дополнительная пространственная сложность — O(1): один проход для суммирования первого окна, затем одно сложение и одно вычитание на каждом шаге. Отдельное суммирование каждого окна требует (n-k+1) × k сложений, то есть O(n·k) — примерно 2.5 × 10^7 при n = 10^4 и k = 5000.

Чем это отличается от задачи о максимальном подмассиве?

Здесь длина фиксирована и равна k, поэтому каждый кандидат — это окно, а скользящая сумма охватывает их все. В задаче о максимальном подмассиве длина не фиксирована, и нужен алгоритм Кадане, который для каждого элемента решает, расширить ли текущий отрезок или начать новый. У окна фиксированной длины такого выбора нет.

Могут ли префиксные суммы тоже решить эту задачу?

Да. Постройте prefix[i] как сумму первых i элементов, и сумма окна, начинающегося с s, равна prefix[s+k] - prefix[s]. Это тоже занимает время O(n), но требует хранения n+1 сумм. Скользящее окно вычисляет те же суммы с помощью двух переменных.

Python

def maxSumSubarray(nums, k):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [4, -1, 3, 7, -2, 5, 1]
k = 3

Ожидается