eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сумчатый волк

Сумчатый волк

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Дана последовательность целых чисел длины n. Найдите в ней непустую подпоследовательность подряд идущих чисел, такую, что сумма чисел в ней максимальна.

Входные данные

Число n (1n10^6) в первой строке. Во второй строке заданы члены последовательности, каждый по модулю не больше 1000.

Выходные данные

Выведите максимальную сумму чисел в непустой подпоследовательности подряд идущих чисел.

Пример

Входные данные #1
6
4 2 3 -7 8 1
Выходные данные #1
11
Входные данные #2
8
2 -1 4 3 -8 6 -3 4
Выходные данные #2
8
Входные данные #3
3
-12 -6 -1
Выходные данные #3
-1