Maximum Product Subarray looks like a cousin of the classic "maximum sum subarray," but a single twist — multiplication — makes it trickier. Two negatives multiply to a positive, so the worst product so far can suddenly become the best. The trick is to carry both.
Problem. Given an integer array nums, find the contiguous subarray with the largest product and
return that product. The array has at least one number.
Example: nums = [2, 3, -2, 4] → answer 6 (the subarray [2, 3] gives 2 × 3 = 6).
The slow way first
The obvious idea: try every subarray, multiply out each one, and keep the biggest. There are O(n²) subarrays, so this is O(n²) time — too slow for a large array.
The question to ask: as I extend the array one number at a time, what do I need to remember to know the best product ending here? For sums it would be just the running best. For products there is a catch: a negative number flips signs, so the smallest (most negative) product so far might become the largest after multiplying. So I have to remember both the max and the min product ending at the current position.
The idea: carry the max and the min
Walk the array once, keeping two running values: curMax (best product ending here) and curMin (worst product ending here). For each new number num, the best product ending at num is one of: num alone, curMax × num, or curMin × num.
When num is negative, multiplying flips the order — the old curMin (a big negative) times num becomes a big positive. So before recomputing, we swap curMax and curMin. After each number, update the global answer ans = max(ans, curMax).
The key insight: tracking only the max is not enough, because a negative number turns the min into the next max. Carrying both keeps us safe.
Walk through it
Step through the animation. The pointer i scans left to right while curMax, curMin, and ans update underneath. Watch the third step: when i lands on -2, the two running values swap before the multiply. By the end, ans = 6 from the subarray [2, 3].
Pseudocode
curMax = curMin = ans = nums[0]
for each num after the first:
if num is negative:
swap curMax and curMin # negative flips best <-> worst
curMax = max(num, curMax * num)
curMin = min(num, curMin * num)
ans = max(ans, curMax)
return ansThe Python solution
def max_product(nums):
curMax = curMin = ans = nums[0]
for num in nums[1:]:
if num < 0:
curMax, curMin = curMin, curMax
curMax = max(num, curMax * num)
curMin = min(num, curMin * num)
ans = max(ans, curMax)
return ans- We seed
curMax,curMin, andansall with the first element — every subarray must contain at least one number. - Lines 4-5 are the heart of the trick: when
numis negative, the biggest and smallest products swap roles, so we exchange them before multiplying. curMax = max(num, curMax * num)either starts fresh atnumor extends the previous best product.curMin = min(num, curMin * num)tracks the most negative product, ready to flip back into a max later.ansrecords the bestcurMaxwe have ever seen, which is the final answer.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (every subarray) | O(n²) (slow) | multiply out each one |
| Track max and min (this solution) | O(n) (moderate) | one pass, O(1) work per step |
O(1) (fast)We make a single pass and keep only three numbers, so the extra space is O(1). The whole win comes from realizing we must carry the min alongside the max.
When this pattern shows up
When a running quantity can flip sign or order as you extend it — products with negatives, or any problem where the worst value can become the best — track both extremes at once. The same carry-max-and-min idea appears in several DP-on-arrays questions.
Do not forget the num alone option inside the max and min. A single very large positive (or a reset
after a zero) means the best subarray sometimes starts fresh at the current number rather than extending
the previous one.
Practice
For nums = [2, 3, -2, 4], when i reaches -2, what happens to curMax and curMin before the multiply, and why?
1. Why do we track curMin as well as curMax?
2. What do we do when the current number is negative?
3. What is the time and space complexity of this solution?
4. Why include num by itself in the max and min, not just the products?