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
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution