ArrayDynamic Programming
Find the contiguous, non-empty subarray with the largest sum and print that sum.
Input
Line 1: n. Line 2: n integers.
Output
Print the maximum subarray sum.
Constraints
1 <= n <= 10^5 -10^4 <= each value <= 10^4
Example 1
Input
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
The subarray [4, -1, 2, 1] sums to 6.