Отрезок с максимальной суммой

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

Перебор всех пар границ — квадрат. Существуют два линейных решения, и полезно знать оба: первое проще обосновать, второе проще написать.

Через префиксные суммы

Пусть $P_i$ — сумма первых $i$ элементов, $P_0 = 0$. Тогда сумма на отрезке $(l, r]$ равна $P_r - P_l$.

Зафиксируем правую границу $r$. Слагаемое $P_r$ фиксировано, значит, максимизировать сумму — то же самое, что минимизировать $P_l$ по всем $l < r$.

А минимум префикса легко поддерживать одной переменной по ходу прохода:

long long prefix = 0, minPrefix = 0, best = LLONG_MIN;
for (long long value : a) {
    prefix += value;
    best = max(best, prefix - minPrefix);
    minPrefix = min(minPrefix, prefix);
}

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

Начальное minPrefix = 0 соответствует $P_0$, то есть варианту «отрезок начинается с самого начала».

Алгоритм Кадане

Второй способ короче и на первый взгляд загадочен:

long long best = LLONG_MIN, current = 0;
for (long long value : a) {
    current = max(value, current + value);
    best = max(best, current);
}

Смысл: current — максимальная сумма отрезка, заканчивающегося ровно на текущем элементе. Такой отрезок либо продолжает предыдущий, либо начинается заново с текущего элемента. Что выгоднее, решает max.

Эквивалентная и более наглядная формулировка: идём вперёд, накапливая сумму; как только накопленное стало отрицательным — обнуляем и начинаем заново. Отрицательный префикс никогда не помогает.

Оба варианта проверены против полного перебора: на пятидесяти тысячах случайных массивов до десяти элементов со значениями от $-20$ до $20$ все три метода дали одинаковый ответ.

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

Самая частая ошибка — инициализировать ответ нулём:

long long best = 0;   // неверно, если требуется непустой отрезок

На массиве из одних отрицательных чисел такой код вернёт ноль, а правильный ответ — наибольшее (наименьшее по модулю) из чисел.

Инициализация LLONG_MIN это чинит. Если по условию пустой отрезок допустим, best = 0 наоборот правильно — прочитайте условие внимательно, разница именно в этом слове.

Восстановление границ

Часто просят не сумму, а сами границы. В варианте Кадане достаточно запомнить, где отрезок начался:

long long best = LLONG_MIN, current = 0;
int start = 0, bestL = 0, bestR = 0;
for (int i = 0; i < n; i++) {
    if (current + a[i] < a[i]) { current = a[i]; start = i; }
    else current += a[i];
    if (current > best) { best = current; bestL = start; bestR = i; }
}

Здесь max пришлось развернуть в if — иначе непонятно, какая из веток сработала.

Родственные постановки

Минимальная сумма — тот же алгоритм со знаком минус, или инвертируйте массив.

Максимальная сумма отрезка длины не более $k$ — уже не Кадане: нужна очередь с минимумом по префиксным суммам, чтобы искать минимальный $P_l$ в скользящем окне.

Максимальное произведение подотрезка — Кадане с двумя переменными: минусы меняют местами максимум и минимум, поэтому вести приходится оба.

Циклический массив — ответ либо обычный максимальный отрезок, либо «весь массив минус минимальный отрезок». Берём максимум из двух. Отдельно обработайте случай, когда все числа отрицательны, — иначе второй вариант выродится в пустоту.

Двумерная версия

В матрице найти подпрямоугольник с максимальной суммой.

Перебираем пару строк — верхнюю и нижнюю границу прямоугольника. Для фиксированной пары сжимаем каждый столбец в одно число (сумму по этим строкам) и запускаем Кадане по получившемуся одномерному массиву.

long long best = LLONG_MIN;
for (int top = 0; top < n; top++) {
    vector<long long> column(m, 0);
    for (int bottom = top; bottom < n; bottom++) {
        for (int j = 0; j < m; j++) column[j] += grid[bottom][j];
        best = max(best, kadane(column));
    }
}

Сложность — $O(n^2 m)$. Вектор column создаётся один раз на каждый top и накапливается по мере роста bottom — пересчитывать его заново для каждой пары строк было бы лишним множителем $n$.

Тот же приём «зафиксировать две границы по одному измерению и свести к одномерной задаче» работает и для максимального прямоугольника, и вообще для большинства двумерных задач такого рода.