Задача A. Максимальная подпоследовательность
Условие
В последовательности из N чисел выделить
подпоследовательность с максимальной суммой элементов.
Формат входного файла
Во входном файле содержится число
N за которым следуют
N целых
чисел
xi — элементы последовательности.
Формат выходного файла
Выходной файл должен содержать единственное число — значение
максимальной суммы.
Ограничения
1 ≤ N ≤ 1000000,
−1000 ≤ xi ≤ 1000.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
4 5 -2 5 -2
|
8
|
