Maximum Subarray (Kadane)

Problem

Find the contiguous subarray with the largest sum and return that sum.

Example

[-2,1,-3,4,-1,2,1,-5,4] -> 6

Constraints

• 1 ≤ n ≤ 10^5

Approach

Kadane's: running sum reset when negative. O(n).