Maximum product subarray in Python

Why this matters

A subarray is a run of neighbouring items in a list. In the list [2, 3, -2, 4], the run 2, 3 is a subarray, and so is the run -2, 4. A run is not a set of items picked from anywhere in the list. The items have to sit next to each other.

The task is to find the subarray whose product is largest. The product of a run is all its numbers multiplied together. For [2, 3, -2, 4] the answer is 6, from the run 2, 3. Multiplying in the -2 gives -12, and multiplying in the 4 after that gives -48, so the run has to stop before the -2.

The problem looks like the sum version, where you want the run with the largest total. Products behave differently. Two negative numbers multiply to a positive number, and a very negative run can turn into a very positive run after one more negative number. This lesson shows how to handle that with one pass over the list.

Every program here is a plain Python file. The programs marked python run print their output without reading input. Run any file with python3 main.py. The outputs shown were produced on Python 3.14.

The problem

Given a list of whole numbers, such as nums = [2, 3, -2, 4], return the largest product of any subarray. The list must have at least one number. An empty list has no answer, and the program in this lesson stops with an error for it.

A subarray has to include at least one number. So if every number is negative, the answer is the least negative number, not 0. The mistakes section shows what goes wrong when the code forgets this.

Step 1: The brute force check

The simplest way to find the answer is to try every subarray. Pick a starting position, then extend the run one number at a time and keep the largest product seen. Two loops do this: the outer loop picks the start, and the inner loop picks the end.

def brute(nums):
    best = None
    for i in range(len(nums)):
        p = 1
        for j in range(i, len(nums)):
            p *= nums[j]
            if best is None or p > best:
                best = p
    return best

The variable best starts as None, which means "no answer yet". The first product always replaces it. In Java the same code starts best at the smallest possible number, but Python needs no such value.

This method is correct, but it is slow. For a list of n numbers, the inner loop runs about n * n / 2 times. For a list of 10,000 numbers that is about 50 million products. The rest of this lesson makes one pass over the list instead, and the brute force method is kept only as a way to check the answer.

Step 2: Why a running product is not enough

A natural idea is to multiply numbers as you go and keep the biggest running product. Try that on [2, 3, -2, 4].

after 2:      product 2
after 3:      product 6      best so far 6
after -2:     product -12    best so far 6
after 4:      product -48    best so far 6

The running product gets worse at the -2, and it never recovers. But the subarray -2, 4 is not the problem. The problem is the running product, which carries the earlier 2, 3 into the calculation. Once the product is negative, the code has no way to know that a later negative number could flip it back to positive.

Now try [-2, 3, 4]. The biggest subarray is the run 3, 4, with product 12. A running product gives -2, then -6, then -24. It never sees the run 3, 4, because the product carried from -2, 3 is too negative. The code needs more than one number to remember.

Step 3: Remember the largest and the smallest

The fix is to track two values at each position, not one.

• max_end is the largest product of a subarray that ends at the current number.
• min_end is the smallest product of a subarray that ends at the current number.

Why the smallest? A negative number multiplied by a negative number gives a positive number, and the most negative product is the one that becomes the largest after a negative number. So when the next number is negative, the old smallest value is the one that might become the new largest.

For each new number x, there are three candidates for the product of a subarray that ends at x.

1. Start a new subarray at x. The product is just x.
2. Extend the old largest product: max_end * x.
3. Extend the old smallest product: min_end * x.

The new max_end is the largest of these three, and the new min_end is the smallest of them. The answer so far is the largest max_end seen at any position.

Here is the rule written as Python code.

a = x
b = max_end * x
c = min_end * x
max_end = max(a, b, c)
min_end = min(a, b, c)
best = max(best, max_end)

Python's max and min take any number of arguments, so the three candidates fit in one call. Python integers never overflow, so the variables need no special width. The mistakes section shows what a fixed-size type does.

Worked example 1: [2, 3, -2, 4]

Start with the first number. At the beginning, the only subarray ending at the first number is the number itself, so max_end, min_end and best all start at nums[0]. Then the rule runs for each later number. The function below prints the values after each step.

The output is:

start  x=2 maxEnd=2 minEnd=2 best=2
i=1 x=3 maxEnd=6 minEnd=3 best=6
i=2 x=-2 maxEnd=-2 minEnd=-12 best=6
i=3 x=4 maxEnd=4 minEnd=-48 best=6

Step i=2 shows the idea at work. The number -2 has the candidates -2, 6 * -2 = -12 and 3 * -2 = -6. The largest is -2, which means the best subarray ending at -2 is -2 alone. The smallest is -12, the product 2, 3, -2. The answer does not change, because best already holds 6 from 2, 3.

Step i=3 shows the smallest value doing its job. The number 4 has the candidates 4, -2 * 4 = -8 and -12 * 4 = -48. Here the largest is 4 alone, so max_end is 4 and the run restarts at 4. The answer stays 6.

Worked example 2: [-2, 3, -4]

This example shows why the smallest value is needed. Start with max_end = -2 and min_end = -2. The trace below comes from the same function as above.

start  x=-2 maxEnd=-2 minEnd=-2 best=-2
i=1 x=3 maxEnd=3 minEnd=-6 best=3
i=2 x=-4 maxEnd=24 minEnd=-12 best=24

At i=2, the number is -4. The candidates are -4, max_end * -4 = 3 * -4 = -12 and min_end * -4 = -6 * -4 = 24. The biggest candidate is 24. That value came from the smallest product at the previous step, which was the run -2, 3 with product -6. Multiplying a negative by a negative gives the large positive answer, 24, from the run -2, 3, -4.

If the code tracked only the largest value, it would multiply the max_end of 3 by -4 and get -12. It would never see the 24. The mistakes section shows that version and its wrong answer.

Worked example 3: [2, -5, -2, -4, 3]

This list has more negative numbers, so the smallest value changes several times. The answer is 24, from the run -2, -4, 3. The trace shows how the values move.

start  x=2 maxEnd=2 minEnd=2 best=2
i=1 x=-5 maxEnd=-5 minEnd=-10 best=2
i=2 x=-2 maxEnd=20 minEnd=-2 best=20
i=3 x=-4 maxEnd=8 minEnd=-80 best=20
i=4 x=3 maxEnd=24 minEnd=-240 best=24

Look at i=2. The number is -2. The candidates are -2, -5 * -2 = 10 and -10 * -2 = 20. The largest is 20, which is the run 2, -5, -2, so max_end becomes 20. The smallest is -2, which is the run -2 alone. Both values are needed at this step.

At i=3, the number is -4. The candidates are -4, 20 * -4 = -80 and -2 * -4 = 8. The smallest, -80, is the run 2, -5, -2, -4, so min_end becomes -80. The largest, 8, is the run -2, -4, so max_end becomes 8.

At i=4, the number 3 has the candidates 3, 8 * 3 = 24 and -80 * 3 = -240. The largest is 24, from -2, -4, 3. The answer becomes 24.

Step 4: The full program with the check

The full program below has the one-pass method, the brute force check, and a list of cases. The output shows that both methods agree on each case. It does not read input.

Output:

[2, 3, -2, 4] -> 6 brute= 6
[-2, 0, -1] -> 0 brute= 0
[-2, 3, -4] -> 24 brute= 24
[2, -5, -2, -4, 3] -> 24 brute= 24
[-5] -> -5 brute= -5
[0, 2] -> 2 brute= 2
[1, -2, 3, -4, 5, -6] -> 360 brute= 360
[-1, -2, -3, 0] -> 6 brute= 6

The [-5] case shows the rule that a subarray must have at least one number. The answer is -5, not 0.

The [-2, 0, -1] case shows a zero. A zero makes every product that touches it equal to 0. The subarray -2 alone is -2, and the subarray -1 alone is -1, so the best choice is a subarray that contains the zero, with product 0.

A random test on 2000 small lists, with a fixed seed, found that the one-pass method matched the brute force method on every list.

Common mistakes

The first mistake is tracking only the largest product. The function below looks reasonable, and it is shorter. The next program runs it on [-2, 3, -4].

The output is:

onlyMax [-2, 3, -4] = 3

The largest product ending at 3 is 3, and multiplying by -4 gives -12. The code never sees the run -2, 3, -4, which has product 24. The correct answer is 24. The smallest value is required, and it cannot be left out.

The second mistake is starting the answer at 0. A common version sets best to 0 so that the first subarray can be compared. This fails when every number is negative. The next program runs that version on [-5].

The output is bestStartsAtZero [-5] = 0. The correct answer is -5, because a subarray must include at least one number, and -5 is the only one. Starting best at nums[0] avoids the problem.

The third mistake is an empty list. Reading nums[0] when the list has no items stops the program with this error:

    max_end = nums[0]
              ~~~~^^^
IndexError: list index out of range

The message says index 0 was read from a list with no items. The fix is to check if not nums: at the start and return an error or a value that the problem defines. The problem statement should say which one.

The fourth mistake is overflow in other languages. Python integers grow to any size, so the product below is exact. In Java, a long holds values up to about 9.2 quintillion, and three numbers of 10 million multiply to 10 to the power of 21, which is larger than that. Java would wrap the value around without a warning. In Python the product is exact:

The output is:

product = 1000000000000000000000

If you use a fixed-size type in another language, check that every product fits, or use a big-integer type. The problem statement should also state a limit if the answer must fit in a fixed size.

Practice

Exercise 1

Find max_product for [0, -3, 0]. Explain the answer in one sentence.

Show the answer

The answer is 0. Any run that includes a zero has product 0. The run -3 alone is -3, which is smaller. So the best run is one that includes a zero.

Exercise 2

Find max_product for [-1, -3, -10, 0, 60]. Name the subarray that gives the answer.

Show the answer

The answer is 60, from the run 60 alone. The run 0, 60 has product 0, the run -10, 0, 60 has product 0, and the run -1, -3, -10 has product -30. A single positive number at the end can beat every run that includes a negative product.

Exercise 3

Find max_product for [-4, -3, -2]. Name the subarray that gives the answer.

Show the answer

The answer is 12, from the run -4, -3. The product of all three numbers is -24, and the run -3, -2 is 6. Two negative numbers next to each other multiply to a positive number, so a pair of them is the best choice here.

Exercise 4

Trace the one-pass method on [2, 3, -2, 4, -1] and find the answer. Write down max_end, min_end and best after each number.

Show the answer

The trace is:

start  x=2 maxEnd=2 minEnd=2 best=2
i=1 x=3 maxEnd=6 minEnd=3 best=6
i=2 x=-2 maxEnd=-2 minEnd=-12 best=6
i=3 x=4 maxEnd=4 minEnd=-48 best=6
i=4 x=-1 maxEnd=48 minEnd=-4 best=48

The answer is 48, from the whole run 2, 3, -2, 4, -1. At i=4, the candidate min_end * x = -48 * -1 = 48 is the largest. This matches the brute force answer, which is also 48.

Exercise 5

Explain why the code computes b and c before it changes max_end and min_end.

Show the answer

The code computes a, b and c from the old values first. The new min_end uses only a, b and c, so changing max_end before that line would not affect it. If the code instead wrote min_end = min(x, max_end * x, min_end * x) after max_end was already updated, the minimum would use the new max_end and give a wrong answer.

Summary

• A subarray is a run of neighbouring numbers, and its product is all of its numbers multiplied together.
• A running product fails because a later negative number can turn a very negative product into a very positive one.
• Track two values at each position: the largest and the smallest product of a subarray ending there.
• For each new number, take the largest and smallest of the number alone, the old largest times the number, and the old smallest times the number.
• The answer is the largest value of max_end seen at any position, which takes one pass and so runs in time proportional to the length of the list.
• Start the answer at the first number, not at 0, and check that the list is not empty.