Problem 4 : Maximum subsequence sum
Problem
Let a_1, a_2, ..., a_n be a sequence of integers. A contiguous subsequence of this sequence is a subsequence a_i, a_i+1, ..., a_j-1, a_j for some i,j such that 1 <= i <= j. You have to write a program which when given a sequence of integers, outputs the maximum possible sum of any contiguous subsequence of the sequence.
Input
First line of the input will be n, the number of integers in the subsequence. n can be as large as upto 100,000. This will be followed by n integers. Each integer will appear on a different line, and there will be no blank lines in the input.
Output
Output the maximum possible sum as defined above.
Sample Input
10
-1
-2
3
-1
4
2
-6
7
-1
5
Sample Output
13