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

Коротко

Сам алгоритм умещается в четыре строки, поэтому на собеседовании важнее другое: объяснить, почему он работает, и не посыпаться на продолжениях. Границы подмассива, циклический массив и ограничение на длину разберём ниже.

Задача

Дан массив целых чисел nums. Нужно найти непрерывный подмассив с наибольшей суммой и вернуть эту сумму. Подмассив содержит хотя бы один элемент.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
ответ: 6, подмассив [4, -1, 2, 1]

Слово «непрерывный» здесь главное. Если бы можно было выбирать любые элементы (подпоследовательность), задача свелась бы к сумме всех положительных чисел. Сложность появляется из-за того, что ради двух хороших кусков иногда приходится взять отрицательное число между ними: в примере это -1.

Перебор: от O(n³) к O(n²)

Самое прямолинейное решение: перебрать все пары границ и для каждой посчитать сумму.

def max_subarray_cubic(nums: list[int]) -> int:
    best = nums[0]
    for l in range(len(nums)):
        for r in range(l, len(nums)):
            best = max(best, sum(nums[l : r + 1]))
    return best

Пар порядка $n^2$, на каждую сумма за $O(n)$, итого $O(n^3)$. Лишняя работа видна сразу: сумма отрезка [l, r] отличается от суммы [l, r - 1] одним слагаемым. Копим её на ходу:

def max_subarray_quadratic(nums: list[int]) -> int:
    best = nums[0]
    for l in range(len(nums)):
        cur = 0
        for r in range(l, len(nums)):
            cur += nums[r]
            best = max(best, cur)
    return best

Это уже $O(n^2)$. При длине $10^5$ получается около $5 \cdot 10^9$ пар, в лимит времени такое не уложится. Но на собеседовании его стоит произнести вслух: от него удобно строить следующий шаг.

Как перейти к одному проходу

Перебор фиксирует левую границу и двигает правую. Поменяем вопрос и зафиксируем правую:

dp[i] — наибольшая сумма подмассива, который заканчивается ровно в позиции i.

Любой подмассив где-то заканчивается, поэтому ответ на всю задачу — это максимум среди всех dp[i].

Теперь посмотрим, каким может быть лучший подмассив, заканчивающийся в i. Вариантов два:

1. Только один элемент nums[i].
2. Элемент nums[i] плюс какой-то подмассив, заканчивающийся в i - 1. Выгоднее всего взять лучший из таких, а его сумму мы уже знаем: это dp[i - 1].

Формулу можно прочитать проще: если накопленная сумма отрицательная, она только мешает, поэтому бросаем её и начинаем заново с текущего элемента.

def max_subarray_dp(nums: list[int]) -> int:
    dp = [0] * len(nums)
    dp[0] = nums[0]
    for i in range(1, len(nums)):
        dp[i] = max(nums[i], dp[i - 1] + nums[i])
    return max(dp)

Это обычная динамика с линейным переходом. Каждому dp[i] нужен только предыдущий элемент, значит, весь массив можно свернуть в одну переменную, а максимум считать на ходу. Так получается тот самый алгоритм Кадане:

def max_subarray(nums: list[int]) -> int:
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best


max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])  # 6
max_subarray([-3, -1, -5])  # -1

То же на JavaScript:

function maxSubArray(nums) {
  let best = nums[0]
  let cur = nums[0]

  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i])
    best = Math.max(best, cur)
  }

  return best
}

Разбор на примере

Пройдём по [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Обратите внимание на строку с i = 4: сумма упала, но подмассив мы не бросаем, потому что хвост 3 всё ещё полезен следующему элементу. Сбрасываемся мы только тогда, когда накопленная сумма отрицательна. Падение ничего не решает: лучший результат уже записан в best.

Сложность и одна придирка

Один проход и две переменные: $O(n)$ по времени и $O(1)$ по памяти.

Есть нюанс, специфичный для Python: срез nums[1:] копирует список, так что версия выше формально расходует $O(n)$ памяти. Если собеседующий придерётся, замените срез на itertools.islice(nums, 1, None) или цикл по индексам.

Кадане — это жадность или динамика? В задаче на сайте стоят оба тега, и оба честные. Выводится алгоритм как динамика, а «бросаем отрицательный хвост» читается как жадное правило. На собеседовании безопаснее объяснять через dp[i]: корректность тогда следует прямо из определения, а жадное правило пришлось бы доказывать отдельно.

Ловушка: все числа отрицательные

Вот версия, которую часто пишут по памяти:

def max_subarray_or_empty(nums: list[int]) -> int:
    best = cur = 0
    for x in nums:
        cur = max(0, cur + x)
        best = max(best, cur)
    return best


max_subarray_or_empty([-3, -1, -5])  # 0

На обычных тестах она работает, а на [-3, -1, -5] возвращает 0 вместо -1. Ноль здесь — сумма пустого подмассива, а условие требует хотя бы один элемент.

Сам код при этом не «неправильный», он решает другую задачу, в которой пустой подмассив разрешён. У этой версии длинная история. Задачу предложил Ульф Гренандер в 1977 году, Майкл Шеймос нашёл решение за $O(n \log n)$ и рассказал о задаче на семинаре в Университете Карнеги — Меллона, а присутствовавший там Джей Кадане, по известному пересказу, придумал линейный алгоритм за минуту. В исходной публикации пустой подмассив разрешён: если положительных чисел нет, ответ равен 0. Вариант с best = nums[0] — адаптация под условие «хотя бы один элемент».

Отсюда практическое правило: прежде чем писать код, спросите, можно ли вернуть пустой подмассив. Иногда ноль как раз и нужен, как в задаче о покупке и продаже акции, к которой мы ещё вернёмся.

Есть ещё одна популярная запись, со сбросом, и в ней важен порядок строк:

def max_subarray_reset(nums: list[int]) -> int:
    best = nums[0]
    cur = 0
    for x in nums:
        cur += x
        best = max(best, cur)  # сначала обновляем ответ
        if cur < 0:
            cur = 0  # и только потом сбрасываем
    return best


max_subarray_reset([-3, -1, -5])  # -1

Если поменять местами обновление best и сброс, best успеет увидеть ноль, и ошибка вернётся.

И ещё: nums[0] падает на пустом массиве. В условии на сайте длина от единицы, но на собеседовании этот случай тоже лучше проговорить.

Минимальный набор тестов, который стоит прогнать в голове: [-3, -1, -5], [5], [0], [-1] и основной пример.

Границы подмассива

Частое продолжение: «а теперь верни сам подмассив». Заведём start — начало текущего подмассива, а left и right будут хранить границы лучшего из найденных.

def max_subarray_bounds(nums: list[int]) -> tuple[int, int, int]:
    best = cur = nums[0]
    left = right = start = 0

    for i in range(1, len(nums)):
        if cur < 0:
            cur = nums[i]
            start = i
        else:
            cur += nums[i]

        if cur > best:
            best = cur
            left, right = start, i

    return best, left, right


max_subarray_bounds([-2, 1, -3, 4, -1, 2, 1, -5, 4])  # (6, 3, 6)
max_subarray_bounds([-3, -1, -5])  # (-1, 1, 1)

Условие cur < 0 — это та же формула, что и раньше: x > cur + x выполняется ровно тогда, когда cur < 0.

Классическая ошибка — присвоить left = i прямо в момент сброса. На [5, -10, 1] сброс случится в конце, left станет равен 2, а right останется равен 0, и получится несуществующий отрезок. Поэтому начало хранится отдельно в start, а left и right меняются вместе и только при улучшении best.

Подмассивов с максимальной суммой может быть несколько, и ответ зависит от двух сравнений:

• cur > best оставляет первый найденный: на [1, -1, 1] это [1]. С cur >= best получим последний: весь массив;
• cur < 0 сохраняет нулевой префикс: на [0, 3] вернётся [0, 3]. С cur <= 0 получим [3].

Если требуют самый короткий подмассив, сравнений мало: на [1, 1, -5, 2] первым найдётся [1, 1], а короче будет [2]. Придётся явно сравнивать длины при равных суммах.

Циклический вариант

Теперь массив замкнут в кольцо: после последнего элемента снова идёт первый. Каждый элемент можно взять только один раз. На LeetCode это задача 918.

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

[ 5, -3, 5 ]
  ^      ^    подмассив через стык: 5 + 5
     ^^       то, что осталось в середине: -3

Подмассив через стык — это всё кольцо минус кусок в середине. Чтобы максимизировать сумму того, что взяли, нужно минимизировать сумму того, что выбросили. Значит, нужен второй проход Кадане, только на минимум:

def max_circular(nums: list[int]) -> int:
    total = best_max = best_min = cur_max = cur_min = nums[0]

    for x in nums[1:]:
        total += x
        cur_max = max(x, cur_max + x)
        best_max = max(best_max, cur_max)
        cur_min = min(x, cur_min + x)
        best_min = min(best_min, cur_min)

    # Все числа отрицательные: total - best_min дал бы пустой подмассив
    if best_max < 0:
        return best_max

    return max(best_max, total - best_min)


max_circular([5, -3, 5])  # 10
max_circular([-3, -2, -3])  # -2

Здесь снова та же ловушка. На [-3, -2, -3] минимальный подмассив — весь массив, и total - best_min равно нулю, то есть сумме пустого подмассива. Без проверки вернётся 0 вместо -2.

Одной проверки хватает. Если best_max >= 0, вырожденный ноль не превысит best_max и на ответ не повлияет. А если минимальный кусок лежит у края массива, остаток оказывается обычным подмассивом без стыка, и это тоже корректный кандидат.

Частая неверная идея — склеить массив с самим собой и запустить Кадане. На [1, 2, 3] склейка даст 12, хотя каждый элемент можно взять один раз и ответ равен 6. Такой подход работает только с ограничением длины, о котором дальше.

Связь с префиксными суммами

Сумма отрезка через префиксные суммы — это разность двух префиксов:

Хотим максимизировать разность при фиксированном r, значит, нужен минимальный префикс среди всех, что были раньше. Получается другая запись той же задачи:

def max_subarray_prefix(nums: list[int]) -> int:
    prefix = 0
    min_prefix = 0
    best = nums[0]

    for x in nums:
        prefix += x
        best = max(best, prefix - min_prefix)
        min_prefix = min(min_prefix, prefix)  # строго после обновления best

    return best


max_subarray_prefix([-2, 1, -3, 4, -1, 2, 1, -5, 4])  # 6
max_subarray_prefix([-3, -1, -5])  # -1

Если сравнить с Кадане, окажется, что это один и тот же алгоритм: на каждом шаге cur == prefix - min_prefix.

«Бросить отрицательный хвост» и «обновить минимальный префикс» — одно и то же событие. Ловушка тоже общая: если обновить min_prefix раньше best, разность станет разрешать пустой отрезок, и на отрицательном массиве снова вернётся 0.

Зачем нужна вторая запись

В Кадане начало подмассива скрыто внутри cur, а префиксы показывают его явно. Поэтому ограничения на длину решаются именно через них.

Длина не меньше k. Минимум берём только среди префиксов, которые стоят минимум на k позиций левее:

def max_subarray_at_least_k(nums: list[int], k: int) -> int:
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)

    best = prefix[k]
    min_prefix = prefix[0]

    for r in range(k, len(nums) + 1):
        min_prefix = min(min_prefix, prefix[r - k])
        best = max(best, prefix[r] - min_prefix)

    return best


max_subarray_at_least_k([-2, 1, -3, 4, -1, 2, 1, -5, 4], 5)  # 5

Длина не больше k. Теперь нужен минимум в скользящем окне префиксов, и здесь работает монотонная очередь:

from collections import deque


def max_subarray_at_most_k(nums: list[int], k: int) -> int:
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)

    best = nums[0]
    window = deque()  # индексы префиксов, значения по возрастанию

    for r in range(1, len(prefix)):
        while window and prefix[window[-1]] >= prefix[r - 1]:
            window.pop()
        window.append(r - 1)
        if window[0] < r - k:
            window.popleft()
        best = max(best, prefix[r] - prefix[window[0]])

    return best


max_subarray_at_most_k([-2, 1, -3, 4, -1, 2, 1, -5, 4], 2)  # 4

Это, кстати, и есть корректная версия идеи со склейкой для кольца: склеиваем массив с собой и ищем лучший подмассив длиной не больше n.

Обычное скользящее окно здесь не сработает: из-за отрицательных чисел сумма не монотонна при сдвиге границ, и непонятно, какую границу двигать.

Покупка и продажа акции. Задача из той же семьи: один раз купить, позже один раз продать. Цены — это префиксные суммы массива дневных изменений, поэтому максимальная прибыль равна максимальной сумме подмассива изменений:

def max_profit(prices: list[int]) -> int:
    best = cur = 0
    for today, tomorrow in zip(prices, prices[1:]):
        cur = max(0, cur + tomorrow - today)
        best = max(best, cur)
    return best


max_profit([7, 1, 5, 3, 6, 4])  # 5
max_profit([7, 6, 4, 3, 1])  # 0

Здесь старт с нуля и есть правильный вариант: можно вообще не торговать, то есть взять пустой подмассив. Та же формула, другое условие, другая инициализация.

Другие варианты

Максимальное произведение подмассива (LeetCode 152). Отрицательное число превращает наименьшее произведение в наибольшее, поэтому одной переменной мало, нужно хранить обе:

def max_product(nums: list[int]) -> int:
    best = hi = lo = nums[0]
    for x in nums[1:]:
        candidates = (x, hi * x, lo * x)
        hi, lo = max(candidates), min(candidates)
        best = max(best, hi)
    return best


max_product([2, 3, -2, 4])  # 6
max_product([-2, 3, -4])  # 24

Прямоугольник с максимальной суммой в матрице. Перебираем пары строк, складываем столбцы между ними в один массив и запускаем Кадане по нему. Для матрицы $R \times C$ это $O(R^2 C)$.

def max_rectangle(matrix: list[list[int]]) -> int:
    rows, cols = len(matrix), len(matrix[0])
    best = matrix[0][0]

    for top in range(rows):
        column_sums = [0] * cols
        for bottom in range(top, rows):
            for c in range(cols):
                column_sums[c] += matrix[bottom][c]
            best = max(best, max_subarray(column_sums))

    return best


max_rectangle([[1, 2, -1], [-3, 4, 2], [1, -1, 3]])  # 9

Разделяй и властвуй. В условии задачи на LeetCode есть продолжение: решить её этим способом. Для каждого отрезка храним четыре числа: сумму, лучший префикс, лучший суффикс и лучший подмассив. Два отрезка сливаются так:

# (сумма, лучший префикс, лучший суффикс, лучший подмассив)
def merge(a, b):
    return (
        a[0] + b[0],
        max(a[1], a[0] + b[1]),
        max(b[2], b[0] + a[2]),
        max(a[3], b[3], a[2] + b[1]),
    )

Учебный вариант считает сумму через середину заново на каждом уровне и работает за $O(n \log n)$. С такой четвёркой слияние стоит $O(1)$, так что всё решение укладывается в $O(n)$ плюс $O(\log n)$ на стек рекурсии. Кадане это не обгоняет, но ту же четвёрку можно положить в узлы дерева отрезков и отвечать на запрос «максимальный подмассив на отрезке [l, r]» при изменяющемся массиве за $O(\log n)$. Кадане так не умеет.

Типичные ошибки

1. best = cur = 0 там, где нужен хотя бы один элемент. Ответ на массиве из отрицательных чисел будет 0.
2. Обновление best только в момент сброса. Последний подмассив останется неучтённым: на [1, 2, 3] вернётся 1.
3. left = i при сбросе. Границы начнут указывать на разные подмассивы, нужен отдельный start.
4. Цикл без проверки best_max < 0 или попытка решить его простой склейкой массива.
5. Переполнение. При ограничениях задачи на сайте сумма не превышает $10^9$ и помещается в int. Но если значения доходят до $10^9$, при той же длине сумма вырастет до $10^{14}$, и в Java понадобится long. В JavaScript числа точны до $2^{53}$, а Python считает с произвольной точностью.
6. Путаница подмассива и подпоследовательности. Уточните условие: для подпоследовательности Кадане не нужен.

На собеседовании

Задача из классических подборок вроде Blind 75 и NeetCode 150, есть она и в нашем разборе задач LeetCode. Готовый код многие знают наизусть, поэтому сам по себе он мало что доказывает. Рабочий порядок ответа такой:

1. Уточните условие. Можно ли вернуть пустой подмассив? Может ли быть пустым вход? Нужна только сумма или ещё и границы? Что делать при равных суммах?
2. Назовите перебор за $O(n^2)$ одной фразой.
3. Дайте определение состояния: cur — лучшая сумма, заканчивающаяся в текущей позиции. Переход после этого очевиден.
4. Напишите код и пройдите его на [-3, -1, -5]. Основной пример проверит идею, а этот проверит инициализацию.

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

Решите задачу из блока ниже без подсказок, а затем допишите к ней возврат границ: на этом шаге обычно и всплывают ошибки, незаметные на готовом коде.