Maximum Product Subarray
Maximum Product Subarray is a medium 1-D Dynamic Programming problem from the Blind 75. The key pattern is track max and min, and a good solution runs in O(n) time.
Problem
Return the largest product of a non-empty contiguous subarray.
Examples
Example 1
Input
[-2,3,-4]Output
24Example 2
Input
[3,5,-1,2]Output
15Example 3
Input
[-2]Output
-2Approach
Keep both the largest and smallest product ending at each position, because a negative number swaps them.
| Pattern | Track max and min |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
Zeros reset both running products.