Looking for the best possible sales streak (even accounting for bad, negative-adjustment days), Shuvo wants the maximum total of any single contiguous stretch of days. Read N integers (can be negative) and print the maximum possible sum of a contiguous, non-empty subarray.
Input
Line1: N. Line2: N integers.
Output
The maximum subarray sum.
Constraints
1 ≤ N ≤ 10^5, |a_i| ≤ 10^4
Sample Input
8 -2 1 -3 4 -1 2 1 -5
Sample Output
6
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.