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

Алгоритм Кадане решает классическую задачу максимального подмассива (Maximum Subarray Problem): дан массив целых чисел $a_1, a_2, \ldots, a_n$, нужно найти непрерывный подмассив с наибольшей суммой. Джозеф Кадане (Joseph Kadane) предложил линейное решение в 1984 году, когда Джон Бентли описывал в колонке «Programming Pearls» в Communications of the ACM свой подход «разделяй и властвуй» за $O(n \log n)$ и поделился задачей с коллегами. Кадане за минуту в голове придумал одномерное динамическое программирование за $O(n)$ и $O(1)$ дополнительной памяти - оценка, которую улучшить невозможно: чтобы хотя бы один раз посмотреть на каждый элемент массива, нужно $\Omega(n)$ операций.

Постановка задачи и три уровня сложности

Формально: дан массив $a_1, \ldots, a_n$, найти пару индексов $1 \leq l \leq r \leq n$, на которой сумма $\sum_{i=l}^{r} a_i$ максимальна. Если в массиве есть хотя бы одно положительное число, ответ положителен. Если все элементы отрицательные - ответ равен максимальному элементу (одиночному, длины 1), и это та самая ловушка, на которой реализации обычно ломаются.

Три подхода с возрастающей хитростью:

• Наивный $O(n^3)$ - перебор всех пар $(l, r)$ и пересчёт суммы заново. Тривиально, на больших $n$ безнадёжно.
• Префиксные суммы $O(n^2)$ - посчитать $S_i = a_1 + \ldots + a_i$, тогда сумма на $[l, r]$ равна $S_r - S_{l-1}$, перебор пар идёт за $O(n^2)$.
• Разделяй и властвуй $O(n \log n)$ (подход Бентли) - рекурсивно решать левую половину, правую половину и подмассив, пересекающий середину; последний считается за $O(n)$ от центра вправо и влево.
• Алгоритм Кадане $O(n)$ - динамическое программирование вдоль массива.

Идея динамического программирования

Введём вспомогательную величину $\text{maxEndingHere}(i)$ - максимальная сумма среди всех подмассивов, заканчивающихся в позиции $i$. Это сужение задачи: вместо всех подмассивов фиксируем правый конец и максимизируем по левому.

Заметим простое тождество. Подмассив, заканчивающийся в $i$ - это либо одиночный элемент $a_i$ (если выгоднее «начать заново» с него), либо продолжение лучшего подмассива, заканчивающегося в $i-1$, плюс $a_i$. Отсюда рекуррентность:

$\text{maxEndingHere}(i) = \max\bigl(a_i,\ \text{maxEndingHere}(i-1) + a_i\bigr).$

Это можно ещё переписать как $\text{maxEndingHere}(i) = a_i + \max(0, \text{maxEndingHere}(i-1))$ - если накопленная сумма ушла в минус, обнуляем её перед добавлением $a_i$. Глобальный ответ:

$\text{maxSoFar} = \max_{1 \leq i \leq n} \text{maxEndingHere}(i).$

Один проход, на каждом шаге две константные операции - вот и весь алгоритм.

Псевдокод

maxEndingHere = a[1]
maxSoFar      = a[1]
for i in 2..n:
    maxEndingHere = max(a[i], maxEndingHere + a[i])
    maxSoFar      = max(maxSoFar, maxEndingHere)
return maxSoFar

Инициализация первым элементом, а не нулём - критична. Если стартовать с $\text{maxSoFar} = 0$, то на массиве $[-3, -1, -4]$ алгоритм вернёт $0$ как «пустой подмассив», а корректный ответ - $-1$. Постановка задачи требует непустого подмассива.

Для восстановления границ $(l, r)$ ведём ещё пару указателей: текущий старт start (обновляется, когда $\text{maxEndingHere}$ перезапускается с $a_i$) и итоговые bestL, bestR (фиксируются вместе с обновлением $\text{maxSoFar}$).

Сложность и почему она оптимальна

Время - $O(n)$. Один проход по массиву, на каждой итерации две сравнения и две арифметические операции. Никаких рекурсий, никаких вспомогательных структур.

Память - $O(1)$ дополнительной. Достаточно двух переменных $\text{maxEndingHere}$ и $\text{maxSoFar}$ - массив $\text{maxEndingHere}[\cdot]$ хранить целиком не нужно, для DP-перехода нужен только предыдущий элемент.

Оптимальность. Любой алгоритм, выдающий правильный ответ на всех входах длины $n$, обязан хотя бы раз прочитать каждый элемент: иначе можно изменить непрочитанный $a_k$ на огромное число и сломать ответ. Значит, нижняя оценка по времени - $\Omega(n)$. Алгоритм Кадане эту нижнюю оценку достигает.

Случай со всеми отрицательными элементами

Самая популярная ошибка реализации - версия с обнулением:

maxEndingHere = 0
maxSoFar      = 0
for i in 1..n:
    maxEndingHere = max(0, maxEndingHere + a[i])
    maxSoFar      = max(maxSoFar, maxEndingHere)

Эта версия отвечает на чуть другую задачу - «максимальная сумма подмассива, включая пустой». На массиве $[-2, -3, -1]$ она вернёт $0$, тогда как канонический Кадане - $-1$. Поведение зависит от того, какая постановка нужна заказчику. На собеседовании всегда уточняют: «допускается ли пустой подмассив?» - это не педантизм, это ровно про эту ловушку.

Безопасная универсальная форма - инициализация первым элементом и шаг $\text{maxEndingHere} \leftarrow \max(a_i, \text{maxEndingHere} + a_i)$. Она корректна для всех случаев, включая массив из одного отрицательного числа.

Сравнение с подходом Бентли $O(n \log n)$

Подход «разделяй и властвуй»: разрезаем массив пополам, рекурсивно ищем ответ слева и справа, и отдельно - лучший подмассив, пересекающий середину. Последний считается за $O(n)$: от середины влево накапливаем суффиксный максимум, вправо - префиксный, и складываем.

Рекуррентность $T(n) = 2T(n/2) + O(n)$ даёт по мастер-теореме $T(n) = \Theta(n \log n)$. На практике медленнее Кадане в разы из-за кэш-промахов и накладных расходов на рекурсию, но это полезное упражнение на парадигму «разделяй и властвуй» - Бентли в той самой колонке использовал задачу как обучающий пример.

Современный взгляд: если асимптотически оптимален $O(n)$, никакой $O(n \log n)$ алгоритм не имеет права на жизнь в продакшене. Кадане выигрывает повсеместно.

Двумерное обобщение: максимальная подматрица

Дана матрица $A$ размером $m \times n$, найти прямоугольную подматрицу с максимальной суммой элементов. Прямой перебор всех подматриц - $O(m^2 n^2)$. Алгоритм Кадане обобщается до $O(n^2 m)$ (или $O(\min(m,n)^2 \cdot \max(m,n))$ при правильном выборе оси).

Идея: перебираем все пары строк $(t, b)$, где $t \leq b$ - это верхняя и нижняя границы будущей подматрицы. Для фиксированной пары строим одномерный массив $c[j] = \sum_{i=t}^{b} A[i][j]$ - столбцовые суммы между этими строками. Лучшая подматрица с границами $(t, b)$ соответствует лучшему подмассиву массива $c[\cdot]$, который мы находим обычным Кадане за $O(n)$.

Перебор пар $(t, b)$ - это $O(m^2)$, а столбцовые суммы можно поддерживать инкрементально (при сдвиге нижней границы $b \to b+1$ обновлять $c[j]$ за $O(n)$). Итого $O(m^2 n)$, или $O(n^3)$ на квадратной матрице. Это всё ещё лучший известный полиномиальный алгоритм - асимптотически точные нижние оценки на эту задачу неизвестны, и попытки опуститься ниже кубики связаны с гипотезой APSP и проблемой умножения матриц.

Применения

• Финансы: максимальная прибыль от одной покупки/продажи акции. Дан вектор цен $p_1, \ldots, p_n$. Если ввести массив разностей $d_i = p_{i+1} - p_i$, то прибыль от покупки в день $l$ и продажи в день $r$ - это $\sum_{i=l}^{r-1} d_i$. Максимизация прибыли = поиск максимального подмассива в $d[\cdot]$ = алгоритм Кадане. LeetCode 121 «Best Time to Buy and Sell Stock».
• Биоинформатика: G+C богатые участки ДНК. Кодируем нуклеотид $+1$, если он $G$ или $C$, и $-1$, если $A$ или $T$. Максимальный подмассив выделяет фрагмент генома с аномально высокой долей G+C - это часто указывает на регуляторные регионы (CpG-острова) или горизонтально перенесённые гены.
• Computer vision. В задачах выделения «самого яркого» прямоугольного региона на разностном изображении (после вычитания фона или порога) применяется именно 2D Кадане - максимизировать сумму пикселей в прямоугольной области.
• Конкурсное программирование. Кадане - базовый кирпич в задачах на подсчёт подмассивов и сегментные деревья с операцией «максимальный подмассив на отрезке» (известная задача, решается через хранение четвёрки (sum, prefMax, sufMax, ansMax) в каждом узле). В одной связке с ним часто идут линейные алгоритмы на строках - например, Z-функция строки и алгоритм Манакера для палиндромов.
• Сигнальная обработка. Поиск максимального отклика на нестационарном временном ряду - Кадане выделяет интервал максимальной концентрации сигнала.

Циркулярная вариация

Если массив циркулярный (последний элемент соседствует с первым), задача распадается на два случая. Случай 1: лучший подмассив не пересекает «склейку» - это обычный Кадане. Случай 2: пересекает склейку, то есть выглядит как «кусок справа + кусок слева». Этот случай эквивалентен следующему: общая сумма массива минус минимальный подмассив (выбрасываемая середина). Алгоритм Кадане применяют дважды - для max и для min - и берут $\max(\text{maxKadane},\ \text{total} - \text{minKadane})$.

Тонкость: если все элементы отрицательные, формула $\text{total} - \text{minKadane}$ даёт $0$ (выбросили всё), что некорректно. В этом случае ответ - обычный максимум.

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

• Обнуляют $\text{maxEndingHere}$ вместо $\max(a_i, \text{maxEndingHere} + a_i)$. Так алгоритм отвечает на задачу «допускается пустой подмассив», возвращая $0$ на полностью отрицательных входах. Если по условию подмассив должен быть непустым - это баг.
• Инициализируют $\text{maxSoFar} = 0$. Та же ловушка. Безопасно стартовать с $\text{maxSoFar} = a_1$ и $\text{maxEndingHere} = a_1$.
• Считают границы $l, r$ через post-processing. Восстановление индексов нужно делать онлайн, поддерживая start, bestL, bestR во время основного цикла. Восстановление после факта по значениям требует ещё одного прохода и легко ошибается на дубликатах максимума.
• Применяют 1D Кадане к матрице построчно. Это найдёт лучшую подматрицу высоты 1, а не настоящий 2D-максимум. Нужен перебор пар строк и сведение к 1D.
• Забывают про переполнение. На массиве из $n = 10^5$ элементов до $10^9$ каждый сумма может достичь $10^{14}$ - int32 не подходит, используйте int64 / long.

FAQ

Чем алгоритм Кадане отличается от подхода «разделяй и властвуй»? Кадане - это динамическое программирование вдоль массива за один проход, $O(n)$ времени и $O(1)$ памяти. Подход Бентли - это рекурсия с разрезанием пополам и отдельным учётом подмассивов через середину, $O(n \log n)$ времени и $O(\log n)$ памяти на стек. Кадане асимптотически и практически лучше; «разделяй и властвуй» интересен как обучающий пример парадигмы и обобщается на задачи, где DP вдоль массива не годится.

Можно ли применить Кадане, если запрещены пустые подмассивы и есть отрицательные элементы? Да, и именно это - каноническая постановка. Инициализируйте $\text{maxEndingHere} = \text{maxSoFar} = a_1$ и идите со $i = 2$. На массиве из одних отрицательных алгоритм вернёт максимальный (наименее отрицательный) элемент, что корректно.

Как алгоритм Кадане связан с задачей покупки-продажи акции? Если перейти от цен $p_i$ к разностям $d_i = p_{i+1} - p_i$, то прибыль от покупки в день $l$ и продажи в день $r$ - это сумма $d_l + d_{l+1} + \ldots + d_{r-1}$. Максимизация прибыли по всем парам $(l, r)$ - это максимальный подмассив массива разностей, который Кадане находит за $O(n)$. Допустимо «не торговать вообще» (прибыль $0$) - тогда используется версия с разрешённым пустым подмассивом и $\text{maxSoFar} \geq 0$.

Коротко

Алгоритм Кадане находит максимальный подмассив за $O(n)$ времени и $O(1)$ дополнительной памяти через одномерное DP: $\text{maxEndingHere}(i) = \max(a_i, \text{maxEndingHere}(i-1) + a_i)$, $\text{maxSoFar} = \max_i \text{maxEndingHere}(i)$. Постановка требует непустого подмассива, поэтому критична инициализация первым элементом, иначе на полностью отрицательных входах алгоритм ошибочно возвращает $0$. Двумерное обобщение работает через перебор пар строк и сведение к 1D за $O(n^3)$; циркулярная версия - через $\text{total} - \text{minKadane}$. На LeetCode «Maximum Subarray» (53) и «Best Time to Buy and Sell Stock» (121), в выделении G+C-богатых участков ДНК и в подзадачах segment tree Кадане - стандартный инструмент, и его линейность невозможно улучшить асимптотически.