Largest Sum Contiguous Subarray (Kadane)

Problem

Find the maximum sum of a contiguous subarray.

Example

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

Constraints

• 1 ≤ n ≤ 10^5

Approach

Kadane's, O(n).