Maximum Product Subarray Visualization & Animation
Finds the maximum product subarray by tracking both max and min products to handle negative flips; O(n).
## What is it?
Find the contiguous subarray within an array that has the largest product. Unlike Maximum Sum Subarray, negative numbers can "flip" to give a large positive product when multiplied by another negative.
## How it works
- Track both the **maximum** and **minimum** product ending at the current position
- At each step, the new max/min can come from three sources: the element alone, max×element, or min×element
- `maxProd = max(arr[i], prevMax * arr[i], prevMin * arr[i])`
- `minProd = min(arr[i], prevMax * arr[i], prevMin * arr[i])`
- Update the global answer with `maxProd`
## When to use
- Maximum product subarray (LeetCode 152)
- Problems where negative numbers can be beneficial in pairs
- Extension: handle zeros by resetting both max and min to 1
## Key Points
- O(n) time, O(1) space
- The key insight: a negative × negative = positive, so keep track of the minimum too
- A zero resets the product; handle by taking max/min of just `arr[i]`
Category: algorithms
Difficulty: intermediate
Time Complexity: O(n)
Space Complexity: O(1)
View Maximum Product Subarray Visualization