Серия на табло

На школьном турнире по лёгкой атлетике тренер записал «настроение команды» по минутам: иногда ребята добавляют уверенности (плюс), иногда теряют (минус). Тренер хочет выбрать один непрерывный отрезок минут — так, чтобы суммарный подъём настроения за этот отрезок был максимальным.

Важно: отрезок должен быть непустым.

Формат ввода

В первой строке дано целое число n — количество минут. Во второй строке дано n целых чисел a1, a2, ..., an — изменение настроения по минутам.

Формат вывода

Выведите одно целое число — максимальную возможную сумму на непустом непрерывном отрезке.

Ограничения

• 2 ≤ n ≤ 35000
• -10^9 ≤ ai ≤ 10^9
• Ответ может не помещаться в 32-битный тип (используйте 64-битную арифметику; в Python это не проблема).

Пример

Ввод:

8
-2 3 1 -5 4 2 -1 3

Вывод:

8

(Максимум даёт отрезок 4 2 -1 3.)

Ключевое наблюдение: если мы хотим максимум на непрерывном отрезке, достаточно идти слева направо и для каждой позиции знать ответ на вопрос: «какая максимальная сумма непустого отрезка, который ОБЯЗАТЕЛЬНО заканчивается здесь?»

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

• состоит только из a[i] (начинаем заново),
• либо это «лучший отрезок, заканчивавшийся в i-1», к которому мы добавили a[i].

Если предыдущая сумма стала отрицательной, тащить её дальше вредно — выгоднее стартовать с текущего элемента.

План решения:

• Прочитайте n и массив a.
• Заводим best_ending = a[0] — лучший отрезок, заканчивающийся в текущей позиции.
• Заводим best = a[0] — ответ среди всех позиций.
• Для каждого следующего x:
• обновите best_ending = max(x, best_ending + x)
• обновите best = max(best, best_ending)
• Выведите best.

Сложность: O(n) по времени и O(1) по памяти.

Частая ошибка: инициализировать best нулём. Отрезок должен быть непустым, поэтому при всех отрицательных числах ответ — максимальный (наименее отрицательный) элемент, а не 0.