57. Maximum Subarray Sum
Challenge1000 ms256 MBSolved by 0%
Find the largest possible sum of any contiguous run of elements in the array, and print it.
The run must contain at least one element, so if every value is negative the answer is the single largest value, not zero.
For [-2, 1, -3, 4, -1, 2, 1, -5, 4] the best run is 4, -1, 2, 1, giving 6.
Constraints - `1 ≤ n ≤ 200000` - `-1000000 ≤ a[i] ≤ 1000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print one integer, the largest sum of any non-empty contiguous run.
Input9
-2 1 -3 4 -1 2 1 -5 4
Output6
Noteis the worked example from the statement
Input5
1 2 3 4 5
Output15
Noteis all positive, so the whole array is the answer
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.