Файлы и большие данные · тема 6 из 8
От полного перебора к O(n)
Оптимизация · тренировочная база для ЕГЭ 27
Одна идея — один пример
Сумму каждого окна длины k можно обновлять: убрать элемент, вышедший слева, и добавить новый справа. Это O(n), вместо пересчёта всех k элементов.
a = [2, 5, 1, 4]
print(sum(a[:2]))Теперь решаем самостоятельно
Лучший результат инициализируют суммой первого окна, а не нулём. Тогда отрицательные данные не ломают ответ.
Первая строка — k. Вторая — список n целых чисел, 1 ≤ k ≤ n. Выведи максимальную сумму k последовательных элементов. Для больших n используй скользящее окно.
Пример входных данных и результата
Ввод:
2 2 5 1 4
Вывод:
7
Черновик и файл программы
Черновик сохраняется в этом браузере. Ctrl/⌘ + S — сохранить.
Результаты проверки
Напиши решение и нажми «Проверить код». Данные каждого теста подаются автоматически.
Нужна подсказка?
Следующее окно: current + a[i] - a[i-k].
На чём легко ошибиться
Это тренировочный алгоритм, а не универсальное решение всех вариантов №27: модель надо выбирать по условию.
Разобрать один из способов решения
Сначала попробуй написать код сам. Сравни алгоритм, затем закрой разбор и воспроизведи решение без подсказки.
k = int(input())
a = list(map(int, input().split()))
current = best = sum(a[:k])
for i in range(k, len(a)):
current += a[i] - a[i-k]
best = max(best, current)
print(best)Тесты проверяют результат на учебных примерах, но не доказывают правильность для любого входа. Объясни каждую строку и предложи собственный тест.
Перед следующей темой
Назови входные данные, результат, основной шаг алгоритма и граничный случай. Если использовал разбор, напиши решение заново. Для свободных экспериментов открой Python онлайн.
Все темы этого курса
Программа подготовлена по темам банка «Академии С». Официальные документы: ФИПИ. Справочник языка: Python. Не все экзаменационные задачи нужно решать программой: например, работа в таблицах требует освоения табличного редактора.