Hardarraysdp
Maximum Subarray Sum
Time limit 2 s · Memory 64 MBAcceptance: 100.0%Solved by: 1
Statement
The first line contains n, the second line contains n integers. Print the largest sum of a non-empty contiguous subarray.
Examples
Example 1
Input
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
Example 2
Input
5 -3 -1 -2 -4 -1
Output
-1
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a_i ≤ 10^9