Problems
Thylacine
Thylacine
Given the sequence of n integers. Find its nonempty subsequence of consecutive numbers, such that the sum of these numbers is maximal.
Input
First line contains number n (1 ≤ n ≤ 106
). Second line contains the sequence elements, each of them is no more than 1000.
Output
Print the maximum sum of numbers in non-empty sub-sequence of consecutive numbers.
Input example #1
6 4 2 3 -7 8 1
Output example #1
11
Input example #2
8 2 -1 4 3 -8 6 -3 4
Output example #2
8
Input example #3
3 -12 -6 -1
Output example #3
-1