Maximum Product Subarray
The problem
Find the largest product of any nonempty contiguous subarray of a nonempty integer array. Values may be positive, negative, or zero.
Example
[-2, 3, -4] → 24
Need a hint?
A very negative product becomes useful when multiplied by another negative value.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Track both the minimum and maximum product ending at the previous index. At value x, the new extremes come from x, x × oldMinimum, and x × oldMaximum. Compute both from the old states, then update the global maximum. Starting anew at x handles zeros and resets.
Complexity
O(n) time and O(1) extra space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.