MediumArraysDynamic ProgrammingSliding Window

Maximum Product Subarray

1 approach, code in every language

Given an integer array, find the contiguous non-empty run of elements whose product is the largest, and return that product. The array may mix positive numbers, negative numbers, and zeros.

Products behave unlike sums because a pair of negatives multiplies into a positive, so a badly small product can suddenly become the best one. That means as you extend the run you have to keep an eye on both the largest and the smallest running product ending at each position.

Example 1

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

Output: 6

The run 2,3 multiplies to 6; the negative value later prevents any longer run from beating it.

Example 2

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

Output: 24

Multiplying all three, two negatives cancel out to give 24, which beats any shorter run.

Constraints

1 ≤ nums.length ≤ 2 * 10^4
-10 ≤ nums[i] ≤ 10
The product of any prefix of the array fits in a 32-bit integer

Track running max and min

Carry both the largest and smallest product ending at the current index, swapping them on negatives, so a future negative can turn the smallest into the largest.

Loading animation…

Intuition

A negative number flips the roles of your best and worst running products: the most negative product suddenly becomes the most positive when multiplied by another negative. So at each step you keep two values, the maximum and minimum product ending here, and when the current element is negative you swap them before updating. Each new product is either the element on its own or the element times the previous running extreme, and the overall answer is the best maximum seen anywhere.

Algorithm walkthrough

1Seed the answer, the running maximum, and the running minimum all with the first element.
2For each following element, if it is negative swap the running maximum and minimum first.
3Set the running maximum to the larger of the element alone or the element times the old running maximum.
4Set the running minimum to the smaller of the element alone or the element times the old running minimum.
5Update the answer with the running maximum, and after the loop return that answer.

Implementation

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        best = nums[0]
        cur_max = nums[0]
        cur_min = nums[0]
        for i in range(1, len(nums)):
            x = nums[i]
            if x < 0:
                cur_max, cur_min = cur_min, cur_max
            cur_max = max(x, cur_max * x)
            cur_min = min(x, cur_min * x)
            best = max(best, cur_max)
        return best

Time

O(n)

Space

O(1)

One pass maintains two running extremes, so no extra storage is required.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Best Multiplier Tile Run is our own problem on the technique behind Maximum Product Subarray: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free