Информатика · ЕГЭ · 4 мин чтения

Как найти максимальную сумму трёх соседних элементов за один проход?

Редакция Алгоса · Обновлено

Короткий ответ

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

Разберись, что нужно найти

Рассмотрим [2, 5, 1, 4, 6] и окна длины три. Первое окно содержит 2, 5, 1, его сумма 8. При сдвиге число 2 выходит, а 4 входит: новая сумма 8 − 2 + 4 = 10. Следующий сдвиг убирает 5 и добавляет 6, получаем 10 − 5 + 6 = 11.

Связь условия задачи с нужным действием
Что дано или требуетсяКак это использовать
Сдвиг вправоУбрать левый, добавить новый правый
currentСумма текущего окна
bestЛучшая сумма среди просмотренных

Проследи решение на конкретных данных

Нужно хранить две величины: сумму текущего окна и максимальную найденную сумму. Они могут отличаться. Если каждый раз присваивать максимуму текущую сумму без сравнения, в конце останется результат последнего окна, а не лучший. Для выбора большего числа в Python подходит max(best, current).

Промежуточные результаты разобранного примера
ШагРезультат
2, 5, 18
5, 1, 410
1, 4, 611
Пример с объяснением
Код:
a = [2, 5, 1, 4, 6]
k = 3
current = sum(a[:k])
best = current
for right in range(k, len(a)):
    current += a[right] - a[right - k]
    best = max(best, current)
print(best)
Вывод равен 11. Индекс right указывает новый правый элемент, right − k — выбывающий слева.

Проверь границы способа и реши сам

Перед запуском проверь 1 ≤ k ≤ len(a). Если список короче окна, полного участка нет. Не начинай best с нуля без причины: при отрицательных числах все суммы могут быть отрицательными, а ноль не соответствует ни одному окну. Отрицательные числа не мешают обновлению суммы окна фиксированной длины.

Самопроверка: для [−5, −1, −3, −2] найди максимальную сумму окна длины два. Выпиши суммы всех трёх окон. Затем объясни, почему похожий метод для окна переменной длины с ограничением на сумму требует дополнительных предположений о числах.

Ответ и почему так

Суммы равны −6, −4 и −5, лучший результат −4. Инициализация нулём дала бы неверный ответ. Здесь длина всегда два, поэтому удаляем и добавляем ровно один элемент. Для переменной длины отрицательные числа могут нарушить предположение, что расширение окна обязательно увеличивает сумму.

Что запомнить

При сдвиге фиксированного окна вычти ушедший элемент и добавь новый; лучший результат начни с первого окна.

Попробовать на Алгосе

Программирование для ЕГЭ

Продолжи подготовку в курсе: разбирай способы решения и проверяй их на самостоятельных заданиях.

Перейти к курсу Все курсы

Источники и материалы

Разобраться дальше

Все вопросы и разборы