1. Идея

Нужно найти максимальную сумму среди всех непустых подотрезков массива.

Перебирать все подотрезки напрямую нельзя: их слишком много, порядка n^2, а n достигает 2 * 10^5.

Ключевая идея такая: будем идти слева направо и для каждой позиции знать:

• cur — максимальная сумма непустого подотрезка, который обязательно заканчивается в текущей позиции;
• ans — максимальная сумма среди всех подотрезков, которые мы уже рассмотрели.

Это и есть алгоритм Кадане.

2. Наблюдения

Рассмотрим элемент a[i]. Если нужен лучший подотрезок, который заканчивается в позиции i, то есть только два варианта:

1. начать новый подотрезок прямо с a[i];
2. продолжить лучший подотрезок, заканчивавшийся в позиции i - 1, добавив к нему a[i].

Значит,

cur = max(a[i], cur + a[i])

После этого обновляем общий ответ:

ans = max(ans, cur)

Почему этого достаточно?

Потому что любой подотрезок, заканчивающийся в i, либо состоит только из одного элемента a[i], либо получается продолжением какого-то подотрезка, заканчивающегося в i - 1. Среди всех таких продолжений выгодно брать именно лучший.

3. Алгоритм

1. Считать n и массив a.
2. Инициализировать:
   • cur = a[0]
   • ans = a[0]
3. Для каждой позиции i от 1 до n - 1:
   • пересчитать cur = max(a[i], cur + a[i])
   • пересчитать ans = max(ans, cur)
4. Вывести ans.

Важно, что подотрезок должен быть непустым. Поэтому нельзя начинать с 0: если все числа отрицательные, ответом должно быть наибольшее из них, а не 0.

4. Почему это работает

Докажем корректность.

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

Покажем, что формула для перехода верна.

Любой непустой подотрезок, заканчивающийся в i, имеет один из двух видов:

• состоит только из элемента a[i];
• получается из некоторого непустого подотрезка, заканчивающегося в i - 1, добавлением элемента a[i].

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

Поэтому лучший подотрезок, заканчивающийся в i, имеет сумму:

max(a[i], previous_cur + a[i])

Именно это и делает алгоритм.

Теперь про ans. После обработки позиции i все подотрезки, которые заканчиваются в одной из позиций от 0 до i, уже учтены. Для каждой позиции мы знаем лучший подотрезок, заканчивающийся там. Значит, если каждый раз делать ans = max(ans, cur), то в ans останется максимум среди всех подотрезков массива.

Следовательно, после завершения алгоритма ans равен максимальной сумме непустого подотрезка.

5. Сложность

Массив просматривается один раз.

• Время: O(n)
• Память: O(1), если не считать хранение входного массива

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long cur = a[0];
    long long ans = a[0];

    for (int i = 1; i < n; i++) {
        cur = max(a[i], cur + a[i]);
        ans = max(ans, cur);
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

cur = a[0]
ans = a[0]

for i in range(1, n):
    cur = max(a[i], cur + a[i])
    ans = max(ans, cur)

print(ans)