Maximum subarray sum
Find the contiguous part of the array (at least one element) with the largest sum, and print that sum.
Reported in: Infosys (SP / DSE), Cognizant GenC (memory-based)
Input
First line: N. Second line: N integers.
Output
The largest subarray sum.
Constraints
1 ≤ N ≤ 10^5; −10^4 ≤ value ≤ 10^4.
Example 1
Input:
9
-2 1 -3 4 -1 2 1 -5 4
Output:
6Example 2
Input:
3
-3 -1 -2
Output:
-1Hint: Kadane's idea: the best sum ending here is either this value alone or this value plus the best sum ending at the previous index.