The problem
Find the contiguous block of numbers with the largest product, and return that product.
Input: [2, −5, −2, −4, 3] Output: 24 (−2 × −4 × 3)
Picture it
Picture a row of multipliers. A minus sign flips everything: the biggest product becomes the smallest and the smallest (most negative) becomes the biggest. So at each step we keep two running values: the largest and the smallest product ending here. A negative number swaps their roles.
How to recognise it
- You want the best value of a contiguous block, like Maximum Subarray, but the value is a product, not a sum.
- Numbers can be negative or zero. A negative flips the sign, so the smallest product so far can become the largest after one more negative.
- A zero resets everything: any block through it has product 0.
- Up to 2 × 10^4 numbers, each between −10 and 10: a nested loop is too slow, a single pass is expected.
- The signal is "running best of a sum-like quantity, but a bad value can turn good". The fix is to track both the best and the worst.
Start with brute force
Try every start, extend the end one number at a time, and keep a running product.
def max_product_brute(nums):
best = nums[0]
for i in range(len(nums)):
prod = 1
for j in range(i, len(nums)):
prod *= nums[j]
best = max(best, prod)
return best
There are about n²/2 blocks. For n = 20,000 that is about 2 × 10^8 multiplications, which is too slow in Python. Space is O(1).
From brute force to the idea
- Think of the sum version. For Maximum Subarray you keep the best block ending at each position. Here the same idea nearly works.
- Why one number is not enough. The best product ending at x could come from the smallest (most negative) product ending just before it:
-8 × -2beats5 × -2. So trackhi, the largest product of a block ending here, andlo, the smallest. - Swap on a negative. If x is negative, multiplying flips the order, so the old
lobecomes the candidate for the newhi. The code swaps them before updating. - Update.
hi = max(x, hi * x)andlo = min(x, lo * x). Thexalone means "start a new block here", which is also what a zero does: bothhiandlobecome 0. - Keep the best.
bestis the largesthiseen anywhere.
This is the key idea: keep both the largest and the smallest product ending at each position, and swap them when a negative arrives.
The key idea
Track both max and min product ending at i; cur_max = max(x, x·prev_max, x·prev_min). O(n).
Python solution
def max_product(nums):
hi = lo = best = nums[0]
for x in nums[1:]:
if x < 0:
hi, lo = lo, hi # a negative swaps big and small
hi = max(x, hi * x)
lo = min(x, lo * x)
best = max(best, hi)
return bestIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): every start with every end | O(1): a running product |
| Track max and min (shown code) | O(n): one pass, a few multiplications per number | O(1): three variables |
Edge cases
- One number (
[-3]): returns-3; the code starts fromnums[0]. - Single zero (
[0]): returns0. - Zero splits the array (
[-2, 0, -1]): returns0. - Two negatives cancel (
[-2, 3, -4]): returns24, the whole array. - Example
[2, 3, -2, 4]: returns6; the negative ends the best block. - Odd number of negatives (
[2, -5, -2, -4, 3]): returns24, from-2 × -4 × 3; including the-5as well would make the product negative. - All negative (
[-1, -2, -3]): returns6, from the first two. - Empty list: raises
IndexErrorbecause ofnums[0]; the problem guarantees at least one number.
Common mistakes
- Tracking only the maximum, as in Maximum Subarray:
[-2, 3, -4]gives 3 instead of 24. - Not swapping on a negative (or swapping after the multiplication), so
hiis built from the wrong value. - Forgetting
xalone in themaxandmin, so a zero or a restart is never possible. - Starting
bestat 0, which is wrong when every number is negative, like[-3].
Return the smallest product of any contiguous block instead. For [2, 3, -2, 4] the answer is -48. Describe your approach, then write it if you like.
Compare with our answer
The same two running values work. The difference is which one you record.
def min_product(nums):
hi = lo = best = nums[0]
for x in nums[1:]:
if x < 0:
hi, lo = lo, hi
hi = max(x, hi * x)
lo = min(x, lo * x)
best = min(best, lo)
return best
min_product([2, 3, -2, 4]) is -48 and min_product([-2, 3, -4]) is -12. Time O(n), space O(1).
A strong answer mentions: that you still need both hi and lo, because the minimum can come from a maximum times a negative, the swap on negatives, and that best now takes the minimum of lo.
1. You must find the contiguous block with the largest product in a list of up to 20,000 integers between −10 and 10. Which approach fits best?
The smallest product ending here can become the largest after a negative, so you need both. Keeping only the best fails on [-2, 3, -4], prefix products break at zeros, and sorting loses contiguity.
2. Why does the shown code run in O(n) time and O(1) space?
The state for a position is hi, lo and best, computed from the previous hi and lo. Zeros are not skipped (they reset the block), and nothing is sorted or filtered.
3. A learner deletes the two lines that swap hi and lo when x is negative. Which input now gives a wrong answer?
For [-2, 3, -4] the best block is the whole array (24), but without the swap the code returns 3. The other inputs have answers (6, 0 and −3) that never need two negatives multiplied together.
Score 60% or more and the lesson is marked complete.