Информатика · ЕГЭ · 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, 1 | 8 |
| 5, 1, 4 | 10 |
| 1, 4, 6 | 11 |
Код:
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. Инициализация нулём дала бы неверный ответ. Здесь длина всегда два, поэтому удаляем и добавляем ровно один элемент. Для переменной длины отрицательные числа могут нарушить предположение, что расширение окна обязательно увеличивает сумму.
Что запомнить
При сдвиге фиксированного окна вычти ушедший элемент и добавь новый; лучший результат начни с первого окна.
Попробовать на Алгосе
Программирование для ЕГЭ
Продолжи подготовку в курсе: разбирай способы решения и проверяй их на самостоятельных заданиях.
Перейти к курсу Все курсы