Maximum Subarray Sum
Find the maximum possible sum of a non-empty contiguous subarray.
Input: the first line has N; the second line has N integers.
Output: the maximum subarray sum.
Constraints:
- 1 ≤ N ≤ 105
- −109 ≤ ai ≤ 109
Sample Tests
Input 1
8 -2 1 -3 4 -1 2 1 -5
Output 1
6
Input 2
3 -3 -1 -2
Output 2
-1
Discussion (opens after you solve — no spoilers before)
No comments yet.