LeetCode 152 · 1-D DP

Maximum Product Subarray, explained with a picture

Multipliers where a minus sign flips everything.

Medium1-D DP
▶ Watch it step by step

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

  1. Think of the sum version. For Maximum Subarray you keep the best block ending at each position. Here the same idea nearly works.
  2. 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 × -2 beats 5 × -2. So track hi, the largest product of a block ending here, and lo, the smallest.
  3. Swap on a negative. If x is negative, multiplying flips the order, so the old lo becomes the candidate for the new hi. The code swaps them before updating.
  4. Update. hi = max(x, hi * x) and lo = min(x, lo * x). The x alone means "start a new block here", which is also what a zero does: both hi and lo become 0.
  5. Keep the best. best is the largest hi seen 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 best

In 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

ApproachTimeSpace
Brute forceO(n²): every start with every endO(1): a running product
Track max and min (shown code)O(n): one pass, a few multiplications per numberO(1): three variables

Edge cases

  • One number ([-3]): returns -3; the code starts from nums[0].
  • Single zero ([0]): returns 0.
  • Zero splits the array ([-2, 0, -1]): returns 0.
  • Two negatives cancel ([-2, 3, -4]): returns 24, the whole array.
  • Example [2, 3, -2, 4]: returns 6; the negative ends the best block.
  • Odd number of negatives ([2, -5, -2, -4, 3]): returns 24, from -2 × -4 × 3; including the -5 as well would make the product negative.
  • All negative ([-1, -2, -3]): returns 6, from the first two.
  • Empty list: raises IndexError because of nums[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 hi is built from the wrong value.
  • Forgetting x alone in the max and min, so a zero or a restart is never possible.
  • Starting best at 0, which is wrong when every number is negative, like [-3].
Your turn: the smallest product

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.

Check what stuck

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?

2. Why does the shown code run in O(n) time and O(1) space?

3. A learner deletes the two lines that swap hi and lo when x is negative. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.