Start learning free

LESSON 447 OF 536 · DYNAMIC PROGRAMMING

Maximum Product Subarray in Python: O(n) Time, O(1) Space

Practice O(n) Read the full explanation

Given a list of integers nums, find the subarray with the largest product and return that product.

A subarray is a run of one or more elements that stand next to each other in nums. Its product is all of its elements multiplied together.

Example 1:

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] has the largest product, 2 × 3 = 6. -2 is the only negative number, so every subarray that includes it has a negative product.

Example 2:

Input: nums = [-2, 0, -1]
Output: 0
Explanation: The answer can't be 2: [-2, -1] is not a subarray, because 0 stands between them. The subarray [0] gives 0, and every other subarray gives 0 or less.

Example 3:

Input: nums = [-2, 3, -4]
Output: 24
Explanation: The whole array: the two negative numbers cancel out, -2 × 3 × -4 = 24.

Constraints:

  • 1 <= len(nums) <= 105
  • -10 <= nums[i] <= 10
  • The product of any subarray of nums fits in a 32-bit integer.

Note:

Your algorithm should run in O(n) time and use O(1) extra space, where n is the length of nums.

STEP 1 OF 9
    Ctrl + Enter to check

    PYTHON · DYNAMIC PROGRAMMING

    Maximum Product Subarray in Python, explained

    Problem overview

    maxProduct receives a list of integers nums and returns the largest product of a subarray. A subarray is a run of one or more elements that stand next to each other, and its product is all of them multiplied together.

    For [2, 3, -2, 4] the answer is 6, from [2, 3]. The only negative number is -2, so every subarray that contains it has a negative product. For [-2, 0, -1] the answer is 0: [-2, -1] is not a subarray, because the 0 stands between the two numbers, and [0] gives 0. For [-2, 3, -4] the answer is 24, from the whole list, since the two negatives cancel out.

    Approach: track the largest and the smallest product ending here

    A maximum-sum scan keeps one running value. Products need two, because of negative numbers: multiplying by a negative flips the order, so the most negative product so far becomes the largest one after the next negative element. For each position, keep:

    • maxHere, the largest product of a subarray that ends at the current element;
    • minHere, the smallest (most negative) such product;
    • result, the largest product seen at any position so far.

    At the next element x = nums[i], the best subarray ending there either starts fresh at x or extends the one ending at the previous element. If x is negative, the two running values swap roles first, because the old minimum times a negative is the new maximum. Starting fresh is also how the product gets past a 0: after a 0, extending gives 0, and the fresh start at the next element is larger.

    Here is the run on [-2, 3, -4]. The first row is the starting values, and each other row shows the values after that element:

    start maxHere=-2 minHere=-2 result=-2
i=1 x=3 maxHere=3 minHere=-6 result=3
i=2 x=-4 maxHere=24 minHere=-12 result=24

    At x = -4 the two values swap first, so maxHere becomes -6 and minHere becomes 3. Then maxHere is the larger of -4 and -6 * -4 = 24, which is 24: the two negatives cancel across the whole list.

    Step by step

    1. Start maxHere at nums[0]. At the first element, the only subarray ending there is the element itself.
    2. Start minHere at nums[0] for the same reason. The smallest product matters because a negative number can turn it into the largest.
    3. Start result at nums[0]. The subarray must have at least one element, so the first element alone is a valid candidate, even when it is negative.
    4. Loop with for i in range(1, len(nums)). Element 0 is already counted.
    5. Swap on a negative. If nums[i] < 0, do maxHere, minHere = minHere, maxHere. Afterwards each variable is the right one to multiply by nums[i].
    6. Update maxHere to max(nums[i], maxHere * nums[i]): start fresh or extend.
    7. Update minHere to min(nums[i], minHere * nums[i]), the same two choices with the smaller one kept.
    8. Update result to max(result, maxHere). The best subarray ends at some element, so checking the best one ending at each element finds it.
    9. Return result after the loop.

    The solution in Python

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

    Python details worth a closer look:

    • Tuple swap. maxHere, minHere = minHere, maxHere evaluates the right side first, so the two names exchange values without a temporary variable.
    • The order of the two updates. Both use the old values. maxHere is changed first, but minHere's formula uses minHere and nums[i] only, so it isn't affected. Writing minHere with maxHere in its formula would be a bug.
    • Built-in max and min. Each takes two or more arguments here and returns the larger or smaller one.
    • No overflow. Python integers grow as needed. The lesson guarantees every subarray's product fits in 32 bits anyway.

    Complexity

    Time: O(n). One pass over the list with a constant amount of work per element.

    Space: O(1). Three variables, whatever the length of nums.

    Edge cases and common mistakes

    • A single element. [-3] returns -3. Starting result at 0 instead of nums[0] would wrongly return 0.
    • Zeros split the list. In [-2, 0, -1], at the 0 both running values become 0, so the earlier -2 can no longer combine with the later -1. The answer is 0. And [0, 2] returns 2: the fresh start after a 0 is what lets the product recover.
    • Keeping only the maximum. Tracking just maxHere fails on [-2, 3, -4], where the best product comes from multiplying a very negative value by another negative.
    • An odd number of negatives. [-2, -3, -4] returns 12, from [-3, -4]: the best subarray leaves one negative out.
    • Forgetting the fresh start. Using only maxHere * nums[i] would keep multiplying by a 0 or a small value forever.

    Testing

    • [2, 3, -2, 4] gives 6.
    • [-2, 0, -1] gives 0.
    • [-2, 3, -4] gives 24.
    • [-3] gives -3.
    • [0, 2] gives 2.
    • [-2, -3, -4] gives 12.
    • [2, -5, -2, -4, 3] gives 24.
    • [1, -1, -1, 0, 5] gives 5.
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free