Алгоритм Кадана: максимальная сумма подмассива в Python

Почему алгоритм Кадана — ваш ключ к задачам на подмассивы

Когда я впервые столкнулся с задачей «найти максимальную сумму непрерывного подмассива», мой мозг лихорадочно искал решение: перебрать все возможные начала и концы? Это O(n²) — как пытаться победить босса, просто зажимая кнопки: бессмысленно и с гарантированным тайм-аутом. Я потратил час, исписывая листы вложенными циклами, тесты падали один за другим, и знакомое чувство безысходности нарастало с каждой секундой таймера.

Но суть задачи не в грубой силе, а в скрытой закономерности. Как только её видишь, решение щёлкает, будто зажигается световой меч в тёмном коридоре. Сегодня я поделюсь с вами инсайтом из динамического программирования (ДП), который превращает, казалось бы, экспоненциальный перебор в элегантный проход за O(n). Этот алгоритм — алгоритм Кадана (Kadane’s algorithm) — обязателен к изучению для каждого, кто готовится к собеседованиям или хочет прокачать навыки решения задач.

Суть алгоритма Кадана: оптимальная подструктура и перекрывающиеся подзадачи

Динамическое программирование применяется, когда задача обладает двумя свойствами: оптимальной подструктурой и перекрывающимися подзадачами. Для максимальной суммы подмассива оптимальная подструктура проста: лучший подмассив, заканчивающийся на позиции i, либо состоит только из nums[i] (мы начинаем заново), либо продолжает лучший подмассив, заканчивающийся на i-1, добавляя nums[i].

Если мы знаем ответ для i-1, то можем вычислить ответ для i за константное время. Не нужно пересматривать предыдущие решения — достаточно хранить текущую «накопительную» сумму.

Рекуррентное соотношение — сердце алгоритма Кадана:

max_ending_here = max(nums[i], max_ending_here + nums[i])
max_so_far = max(max_so_far, max_ending_here)

Почему это работает? Представьте, что вы идёте по тропе, собирая самоцветы (положительные числа) и иногда попадая в ямы (отрицательные числа). На каждом шаге вы спрашиваете: «Оставить ли мешок с камнями, который я несу, или выбросить его и начать новый здесь?» Если текущий камень делает мешок тяжелее, чем если начать заново, вы продолжаете нести; иначе — бросаете старый мешок и начинаете новый. Самый тяжёлый мешок, который вы когда-либо видели, и есть ответ.

Это красивый пример ДП: мы не храним таблицу всех сумм подмассивов, а лишь две переменные, которые резюмируют всю необходимую информацию о пройденном префиксе.

Реализация на Python: от грубой силы к оптимальному решению

Грубая сила — путь в никуда

def max_subarray_bruteforce(nums):
    best = float('-inf')
    for i in range(len(nums)):
        current = 0
        for j in range(i, len(nums)):
            current += nums[j]  # сумма nums[i..j]
            if current > best:
                best = current
    return best

Два вложенных цикла → O(n²) по времени и O(1) по памяти. Для массива из 10⁵ элементов (часто встречается на собеседованиях) это время ожидания сравнимо с попыткой эвока убежать от звёздного разрушителя.

Победа: алгоритм Кадана на Python

def max_subarray_kadane(nums):
    # Обрабатываем случай всех отрицательных чисел, инициализируя первым элементом
    max_ending_here = max_so_far = nums[0]
    for x in nums[1:]:
        # Либо продолжаем предыдущий подмассив, либо начинаем заново с x
        max_ending_here = max(x, max_ending_here + x)
        # Сохраняем лучший результат, который видели
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Почему это O(n)? Один проход по списку, константная работа на каждом элементе. Память — O(1), всего две скалярные переменные.

Типичные ловушки и как их избежать

• Забыли обработать массив из всех отрицательных чисел: возвращается 0 (пустой подмассив), хотя по условию нужен хотя бы один элемент. Решение: инициализируйте обе переменные значением nums[0] (или используйте -inf и обновляйте внутри цикла).
• Использование max_ending_here = max(0, max_ending_here + x): это сбрасывает сумму на ноль при отрицательных числах, ломая случай всех отрицательных. Используйте форму max(x, ...), если только задача явно не разрешает пустой подмассив.

Алгоритм Кадана в реальных задачах с собеседований

LeetCode 53 — Maximum Subarray

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

LeetCode 121 — Best Time to Buy and Sell Stock

Преобразуйте цены в разницу дневных изменений: profit[i] = price[i] - price[i-1]. Максимальная прибыль — это максимальная сумма подмассива этого массива разниц. Снова алгоритм Кадана, но в маскировке.

Обе задачи на первый взгляд выглядят по-разному, но лежащее в основе ДП идентично. Умение замечать такие сходства — признак сильного алгоритмического мышления, которое ценят интервьюеры.

Почему алгоритм Кадана важен за пределами собеседований

Освоение алгоритма Кадана развивает навыки, которые пригодятся в реальной разработке:

• Выявление двух столпов ДП — оптимальной подструктуры и перекрывающихся подзадач — в неочевидных задачах.
• Сжатие состояния — понимание, что часто не нужна полная таблица, достаточно нескольких «скользящих» переменных.
• Трансляция задач (торговля акциями, анализ последовательностей, некоторые варианты поиска кратчайших путей) в форму максимального подмассива.

Когда вы смотрите на задачу и шепчете: «Эй, это же просто бегущая сумма с опцией сброса», — вы переходите из категории «кодер» в категорию «алгоритмический волшебник». Это тот уровень понимания, который открывает новые возможности, как получение новой способности в RPG — следующий босс кажется уже не таким страшным.

Практическое задание: закрепите навык прямо сейчас

Возьмите лист бумаги (или откройте любимую IDE) и попробуйте решить такую задачу:

Дан массив целых чисел. Найдите длину самого длинного подмассива, сумма которого неотрицательна.

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

Напишите своё решение в комментариях, поделитесь озарениями или спросите, где застряли. Продолжим наше приключение — впереди ещё много драконов, и алгоритм Кадана — меч, который поможет их победить. Удачного кодинга! 🚀