Thylacine#5331
Given a sequence of integers, find a non-empty contiguous subsequence with the maximum possible sum.
The first line contains the integer (1 \leq n \leq 10^6). The second line contains integers a_1, a_2, \ldots, a_n (|a_i| \leq 1000 for all ).
Print the maximum sum of numbers in any non-empty contiguous subsequence.
Example 1
Example 2
Example 3