Задача A. Максимальная подпоследовательность

Автор:stdalg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:1 Мб
Выходной файл:output.txt  

Условие

В последовательности из N чисел выделить подпоследовательность с максимальной суммой элементов.

Формат входного файла

Во входном файле содержится число N за которым следуют N целых чисел xi — элементы последовательности.

Формат выходного файла

Выходной файл должен содержать единственное число — значение максимальной суммы.

Ограничения

1 ≤ N ≤ 1000000, 1000 ≤ xi ≤ 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 5 -2 5 -2
8

0.034s 0.008s 15