Подмассив с максимальной суммой: алгоритм Кадане
В этом уроке вы с помощью алгоритма Кадане найдёте непрерывный участок с максимальной суммой за один проход.
Введение
Какую задачу это решает
Каким был лучший период для акции, самый результативный отрезок сезона, самый прибыльный участок поездки? Всё это задачи о максимальном подмассиве. Перебирать все начала и концы долго, а алгоритм Кадана решает задачу за один проход.
Пример из жизни
Алгоритм Кадана похож на прогулку по дороге, где вы собираете золото и платите пошлины. Вы держите кошелёк для текущего отрезка. Когда кошелёк уходит в минус, нести его дальше только во вред, поэтому вы его бросаете и начинаете заново. Ещё вы помните самый полный кошелёк, который у вас когда-либо был.
current = max(value, current + value)👛 Оставить кошелёк или начать заново, если с ним хужеbest = max(best, current)🏆 Запомнить самый полный кошелёкcurrent = best = values[0]🚩 Начать с первого отрезка6💰 Лучший отрезок: 4, -1, 2, 1Задача о максимальном подмассиве просит найти наибольшую сумму идущих подряд элементов списка. Алгоритм Кадана решает её за время O(n): он отслеживает лучшую сумму отрезка, который заканчивается в каждой позиции.
Главное
current- лучшая сумма отрезка, который заканчивается на текущем значении.current = max(value, current + value)начинает новый отрезок, когда старый только уменьшил бы сумму.best = max(best, current)хранит лучшую сумму, найденную до сих пор в любом месте списка.- Обе переменные начинаются с
values[0], поэтому код правильно работает и для списков из одних отрицательных чисел.
Когда это нужно?
- Лучший период во временных рядах: прибыль, баллы, температура.
- Знакомство с классической идеей динамического программирования за один проход.
- Вопросы на собеседованиях о массивах.
Когда это не нужно
- Нужны начало и конец лучшего отрезка: отслеживайте индексы вместе с суммами.
- Значения стоят не в осмысленном порядке: тогда идущие подряд отрезки не имеют смысла.
Пример кода
def maximum_subarray_sum(values):
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
Результат выполнения
6
Разбор кода
Для каждого элемента переменная current выбирает из двух вариантов: начать новый участок с этого элемента или продолжить предыдущий через current + value. Переменная best хранит наибольшую встреченную сумму. На примере данных максимальную сумму 6 даёт участок [4, -1, 2, 1]. Алгоритм работает за O(n) и использует O(1) памяти.
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Начальное значение 0
Если все числа отрицательные, ответ ошибочно получится 0.
current = best = 0
current = best = values[0]
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Максимум в скользящем окне Для каждого окна из k чисел выведите максимум. Сложно
- Largest Adjacent-Digit Product Take every contiguous window of span digits and multiply its digits. Средне