Алгоритмы на Python

Подмассив с максимальной суммой: алгоритм Кадане

В этом уроке вы с помощью алгоритма Кадане найдёте непрерывный участок с максимальной суммой за один проход.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Каким был лучший период для акции, самый результативный отрезок сезона, самый прибыльный участок поездки? Всё это задачи о максимальном подмассиве. Перебирать все начала и концы долго, а алгоритм Кадана решает задачу за один проход.

Пример из жизни

Алгоритм Кадана похож на прогулку по дороге, где вы собираете золото и платите пошлины. Вы держите кошелёк для текущего отрезка. Когда кошелёк уходит в минус, нести его дальше только во вред, поэтому вы его бросаете и начинаете заново. Ещё вы помните самый полный кошелёк, который у вас когда-либо был.

От платной дороги к коду
current = max(value, current + value)👛 Оставить кошелёк или начать заново, если с ним хуже
best = max(best, current)🏆 Запомнить самый полный кошелёк
current = best = values[0]🚩 Начать с первого отрезка
6💰 Лучший отрезок: 4, -1, 2, 1
Продлевайте отрезок, пока это выгодно, а когда нет - начинайте заново.
Одним предложением

Задача о максимальном подмассиве просит найти наибольшую сумму идущих подряд элементов списка. Алгоритм Кадана решает её за время O(n): он отслеживает лучшую сумму отрезка, который заканчивается в каждой позиции.

Главное

  1. current - лучшая сумма отрезка, который заканчивается на текущем значении.
  2. current = max(value, current + value) начинает новый отрезок, когда старый только уменьшил бы сумму.
  3. best = max(best, current) хранит лучшую сумму, найденную до сих пор в любом месте списка.
  4. Обе переменные начинаются с values[0], поэтому код правильно работает и для списков из одних отрицательных чисел.

Когда это нужно?

  • Лучший период во временных рядах: прибыль, баллы, температура.
  • Знакомство с классической идеей динамического программирования за один проход.
  • Вопросы на собеседованиях о массивах.

Когда это не нужно

  • Нужны начало и конец лучшего отрезка: отслеживайте индексы вместе с суммами.
  • Значения стоят не в осмысленном порядке: тогда идущие подряд отрезки не имеют смысла.

Пример кода

Запустить код →
main.py
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.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Начальное значение 0

Если все числа отрицательные, ответ ошибочно получится 0.

Ошибка
current = best = 0
Исправление
current = best = values[0]

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи