1. Идея

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

Ключевая мысль задачи уже заложена в формулировке через префиксные суммы.

Обозначим pre[k] как сумму первых k элементов:

• pre[0] = 0
• pre[1] = a_1
• pre[2] = a_1 + a_2
• ...
• pre[n] = a_1 + ... + a_n

Тогда сумма на отрезке от l + 1 до r равна pre[r] - pre[l].

Если мы хотим найти лучший отрезок, который заканчивается в позиции r, то нужно максимизировать pre[r] - pre[l].
Для фиксированного r это достигается тогда, когда pre[l] минимально среди всех предыдущих префиксов.

Значит, достаточно идти слева направо и поддерживать:

• текущую префиксную сумму pre
• минимальную префиксную сумму min_pre, встреченную раньше
• лучший ответ ans

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

Наблюдение 1

Сумма любого подотрезка выражается через префиксные суммы:

sum(l+1..r) = pre[r] - pre[l]

То есть вместо перебора всех отрезков можно рассматривать разность двух префиксов.

Наблюдение 2

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

Если текущая префиксная сумма равна pre, а минимальный префикс до этого был min_pre, то лучший отрезок, заканчивающийся здесь, имеет сумму:

pre - min_pre

Наблюдение 3

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

• сначала мы добавляем текущий элемент в pre
• только потом пробуем обновить ответ

Значит, рассматриваются только отрезки, содержащие хотя бы текущий день.

Наблюдение 4

Если все числа отрицательные, ответ всё равно существует: это максимальный из элементов массива.

Наш способ корректно это обработает. Например, при первом элементе x:

• pre = x
• ans = max(ans, x - 0) = x

3. Алгоритм

1. Считываем n.
2. Инициализируем:
   • pre = 0 — текущая префиксная сумма
   • min_pre = 0 — минимальная префиксная сумма среди уже просмотренных
   • ans — очень маленькое число
3. Для каждого элемента x:
   1. прибавляем его к pre
   2. пробуем улучшить ответ значением pre - min_pre
   3. обновляем min_pre = min(min_pre, pre)
4. Выводим ans.

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

Докажем, что алгоритм действительно находит максимальную сумму непустого подотрезка.

Пусть мы находимся в некоторой позиции r. После прибавления a_r переменная pre равна pre[r].

Любой подотрезок, который заканчивается в r, имеет вид [l+1, r], где 0 <= l < r, и его сумма равна:

pre[r] - pre[l]

Для фиксированного r значение pre[r] уже известно, поэтому максимальная сумма такого отрезка получается тогда, когда pre[l] минимально среди всех допустимых l.

Именно это значение и хранится в min_pre.

Следовательно, на шаге r величина pre - min_pre — это максимальная сумма среди всех подотрезков, заканчивающихся в r.

Дальше алгоритм берёт максимум по всем r, значит в ans окажется максимальная сумма среди всех непустых подотрезков массива.

Почему обновление min_pre нужно делать после обновления ans?
Потому что min_pre должен соответствовать только префиксам до текущей позиции, иначе можно было бы вычесть текущий же префикс и получить пустой отрезок.

Значит, алгоритм корректен.

5. Сложность

Мы один раз проходим по массиву.

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

Нужно использовать 64-битный тип, потому что сумма может быть большой по модулю.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    long long pre = 0;
    long long min_pre = 0;
    long long ans = -(1LL << 60);

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        pre += x;
        ans = max(ans, pre - min_pre);
        min_pre = min(min_pre, pre);
    }

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

7. Код на Python 3

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

pre = 0
min_pre = 0
ans = -10**30

for x in a:
    pre += x
    ans = max(ans, pre - min_pre)
    min_pre = min(min_pre, pre)

print(ans)