Maximum Product Subarray

The problem

Given an array of integers nums, find the non-empty subarray, a run of numbers next to each other, whose numbers multiply to the largest product. Return that product.

Example 1

Input: nums = [2, -5, 3, -2, 0, 4]

Output: 60

2 × −5 × 3 × −2 = 60. The two negatives cancel out. The 0 cuts the array, so nothing can reach past it.

nums

20-5132-230445

Example 2

Input: nums = [-3, 0, -1]

Output: 0

Every subarray without the 0 is negative, so the 0 alone is best.

Example 3

Input: nums = [-2, -4, -3]

Output: 12

−4 × −3 = 12. Taking all three gives −24.

Constraints

• 1 ≤ nums.length ≤ 20,000 (call it n)
• −10 ≤ nums[i] ≤ 10
• The product of any subarray fits in a 32-bit integer.

Clarifying questions

Can the subarray be empty?

No. It has at least one number, so a lone negative number can be the answer.

Must the numbers be next to each other?

Yes. A subarray is a run, not any pick of numbers.

Can there be zeros?

Yes. A zero makes any product through it 0.

Can the product overflow?

No. Every subarray product is promised to fit in 32 bits.

Spot the pattern

The best subarray ending at each number can be built from the best one ending just before it. That is dynamic programming over positions, the same idea as Maximum Subarray, which sums instead. The twist is the sign: a negative number turns the smallest product into the largest. So we carry two answers, the largest and the smallest, instead of one.

Solutions

Every subarrayO(n²)Largest and smallest so farO(n)

Show all

There is no middle approach worth its own tab. Splitting the array at zeros and counting negatives also gives O(n), but it needs more special cases than tracking two numbers.

Every subarray O(n²)

The idea

Try every start i. From there, grow the subarray to the right one number at a time and multiply it in, so each product reuses the one before instead of starting over. Keep the largest product seen.

Why it is correct: every subarray is some start and some end, and every pair is tried.

Walkthrough

nums

20-5132-230445

best

2

1. best = nums[0]
2. for i in 0 .. len(nums) - 1:
3. product = 1
4. for j in i .. len(nums) - 1:
5. product *= nums[j]; best = max(best, product)
6. return best

Try every subarray. For each start i, grow the subarray to the right and multiply in one number at a time, so each new product reuses the one before.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: for every start, extend the subarray one number at a time and
    // keep a running product. Every subarray is tried once: O(n²) time, O(1) space.
    public int maxProduct(int[] nums) {
        int best = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int product = 1;
            for (int j = i; j < nums.length; j++) {
                // Reuse the product of nums[i..j-1] instead of starting over.
                product *= nums[j];
                best = Math.max(best, product);
            }
        }
        return best;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The inner loop does one multiplication and one max. That is a fixed job, so each run of the inner loop counts as 1 step.

   1. best = nums[0]
   2. for i in 0 .. len(nums) - 1:
   3. product = 1
   4. for j in i .. len(nums) - 1:
   5. product *= nums[j]; best = max(best, product)
   6. return best

2. 2 Count the runs on Example 1

   The table has one column per start. Start 0 grows to 6 numbers, start 5 has only itself.

   6 + 5 + 4 + 3 + 2 + 1 = 21 runs.

   start i	0	1	2	3	4	5
   inner runs	6	5	4	3	2	1

   total

   6 + 5 + 4 + 3 + 2 + 1 = 21 runs

3. 3 Write the count for any n

   The inner loop runs n − i times for start i:

   n + (n − 1) + … + 1 = n × (n + 1) / 2 runs

   Check it with Example 1: 6 × 7 / 2 = 21. That matches the count.

4. 4 Keep only the part that grows fastest

   That is n² / 2 + n / 2. Drop the n / 2 and the 1/2. What is left is n². For 20,000 numbers, that is 200 million steps.

   So the time is O(n²).

5. S Space: count the extra memory the same way

   Only best and the running product. So the space is O(1).

   bestproduct

Largest and smallest so far O(n)

The idea

Walk left to right and keep two numbers about the subarrays that end at the current number:

• largest, the largest product of such a subarray, and
• smallest, the smallest one, usually a big negative number.

For the next number, a subarray ending at number is either number alone, or a subarray ending just before it with number added. Adding number multiplies the product by number. So the new largest is the largest of number, largest × number and smallest × number, and the new smallest is the smallest of the three. Keep the best largest ever seen.

smallest matters because of signs. If number is negative, the smallest product times number becomes the largest. number alone matters because of zeros: after a 0, both products are 0, and a fresh start is better.

Why it is correct: multiplying by number is largest either from the largest earlier product (when number is positive) or from the smallest one (when number is negative). Keeping both means the best subarray ending at every position is found, and the answer ends somewhere.

Walkthrough

nums

20-5132-230445

largest

2

smallest

2

best

2

1. largest = smallest = best = nums[0]
2. for number in nums[1:]:
3. choices = (number, largest * number, smallest * number)
4. largest = max(choices)
5. smallest = min(choices)
6. best = max(best, largest)
7. return best

Walk left to right. largest and smallest are the largest and smallest product of a subarray that ends at the current number. Both start at 2.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Track the largest and smallest product ending here: a negative number turns
    // the smallest into the largest, so both are needed. One pass: O(n) time, O(1) space.
    public int maxProduct(int[] nums) {
        int largest = nums[0], smallest = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int number = nums[i];
            // Start fresh at x, or extend the best or worst run that ended just before.
            int withLargest = largest * number, withSmallest = smallest * number;
            largest = Math.max(number, Math.max(withLargest, withSmallest));
            smallest = Math.min(number, Math.min(withLargest, withSmallest));
            best = Math.max(best, largest);
        }
        return best;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The loop body does two multiplications, a max, a min and one more max. That is a fixed job, so each run of the loop counts as 1 step.

   1. largest = smallest = best = nums[0]
   2. for number in nums[1:]:
   3. choices = (number, largest * number, smallest * number)
   4. largest = max(choices)
   5. smallest = min(choices)
   6. best = max(best, largest)
   7. return best

2. 2 Count the runs on Example 1

   The loop runs once for each number after the first.

   5 runs.

   index	1	2	3	4	5
   loop runs	1	1	1	1	1

   total

   5 runs

3. 3 Write the count for any n

   n − 1 runs

   Check it with Example 1: 6 − 1 = 5. That matches the count.

4. 4 Keep only the part that grows fastest

   Drop the − 1. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   Three numbers, whatever n is. So the space is O(1).

   largestsmallestbest

Common mistake

Updating hi before using it for lo

The new smallest needs the old largest. If the code writes largest = max(...) and then computes smallest from the new largest, the wrong product is used. Work out both products first, then update both.

Tested at the limits

2,000 random arrays of 1 to 10 numbers from −3 to 3, so zeros, sign flips and single negative numbers come up often. Every subarray and largest and smallest so far gave the same answer every time.

Largest inputs	Result
20,000 numbers (the most allowed): short runs of −2, −1, 1 and 2 between zeros, so the sign flips often. Largest and smallest so far.	Under 0.01 s, and under 0.001 MB of extra memory: just the two products and the best.
2,000 numbers. Every subarray, about 2 million of them.	0.08 s. At 20,000 numbers it would try 200 million, 100 times more.