Гиперпереход ( номер на сайте 1296)

Автор задачи:Ден Расковалов

Гиперпереход, открытый еще в начале XXI-го века, и сейчас остается основным способом перемещения на расстояния до сотен тысяч парсеков. Но совсем недавно физиками открыто новое явление. Оказывается, длительностью альфа-фазы перехода можно легко управлять. Корабль, находящийся в альфа-фазе перехода, накапливает гравитационный потенциал. Чем больше накопленный гравитационный потенциал корабля, тем меньше энергии потребуется ему на прыжок сквозь пространство. Ваша цель – написать программу, которая позволит кораблю за счет выбора времени начала альфа-фазы и ее длительности накопить максимальный гравитационный потенциал.

В самой грубой модели грави-интенсивность – это последовательность целых чисел p_i (1 <= i <= n). Будем считать, что, если альфа-фаза началась в момент i, и закончилась в момент j, то накопленный в течении альфа-фазы потенциал – сумма всех чисел, стоящих в последовательности на местах от i до j.

Исходные данные. В первой строчке входа записано число n – число чисел в последовательности, отвечающей за грави-интенсивность (n<60000). Далее идут n строк, в каждой записано целое число p_i (-30000 <= p_i <= 30000). Первая строчка содержит p₁, вторая - p₂ и т.д.

Результат. Максимальный гравитационный потенциал, который может накопить корабль в альфа-фазе прыжка. Считается, что потенциал корабля в начальный момент времени равен нулю.

Примеры.

Решение. Если вам понятны результаты приведенных тестов, то и алгоритм должен быть понятен. Последовательно считываем и суммируем числа. Отслеживаем максимальную сумму. Если сумма становится меньше нуля, обнуляем ее и продолжаем суммирование. Массив, естественно, не нужен. Решайте самостоятельно и сдавайте. Успеха!