Maximum Subarray
Maximum Subarray is a medium Greedy problem from the Blind 75. The key pattern is kadane's algorithm, and a good solution runs in O(n) time.
Problem
Return the greatest sum of a non-empty contiguous subarray.
Examples
Example 1
Input
[-4,2,-1,5,-3]Output
6Example 2
Input
[-3,4,-1,2,-6,5]Output
5Example 3
Input
[1]Output
1Approach
At each value, either extend the best subarray ending at the previous position or start fresh here, and keep the best seen.
| Pattern | Kadane's algorithm |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
With all negative values the answer is the largest single value.