MediumArrayDynamic ProgrammingUpdated Sep 2026

152. Maximum Product Subarray

Asked at Google, Meta, Amazon, Microsoft and 4 more

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

8

Problem

You are given an integer array nums. Find a contiguous subarray (a block of neighboring elements, at least one element long) whose product is as large as possible, and return that product.

The tricky part is that negative numbers can flip the sign. Two negatives multiplied together give a positive, so a very negative product can suddenly become the best one. This is why you cannot simply keep the running maximum like you would for a maximum-sum problem.

A single element is a valid subarray, so its value is always a candidate answer. The answer is guaranteed to fit in a 32-bit integer.

Pick a neighboring block with the biggest product

numsproduct 623-240123The block [2,3] is contiguous and gives the largestproduct.
In [2,3,-2,4] the best block is [2,3], whose product is 6.

Constraints

  • ●1 <= nums.length <= 2 * 10^4
  • ●-10 <= nums[i] <= 10
  • ●The product of any subarray of nums fits in a 32-bit integer.

Examples

Example 1
Inputnums = [2,3,-2,4]
Output6
WhyThe subarray [2,3] multiplies to 6. Any block that includes -2 becomes negative or smaller, so 6 is the best.
Example 2
Inputnums = [-2,0,-1]
Output0
WhyThe product of [-2,-1] would be 2, but those two elements are not next to each other, so that block is not allowed. The best real block is [0], giving 0.

Asked At

8 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
UberMediumView all Uber questions →
WalmartMediumView all Walmart questions →
LinkedInMediumView all LinkedIn questions →

How to Think About It

1

Unlike maximum sum, products can flip sign. A negative times a negative becomes positive. So the minimum product at position i-1 can become the maximum at position i.

2

Track both maxProd and minProd at each position. When nums[i] is negative, swap them (the max becomes min and vice versa).

3

At each element, the candidates are: the element itself (start fresh), maxProd × element (extend max), minProd × element (extend min, might flip to positive).

4

Why it works: by tracking both max and min, you handle the sign-flip property of multiplication.

5

Edge cases: single element (return it), all negatives (pair them), zeros (reset).

Optimal Approach

Step 1: Initialize maxProd = minProd = result = nums[0].
Step 2: For each num in nums[1:]:
If num < 0, swap maxProd and minProd.
maxProd = max(num, maxProd × num)
minProd = min(num, minProd × num)
result = max(result, maxProd)
Step 3: Return result.

Time: O(n). Space: O(1).

Track both the max and the min product

nums23-240123iAfter 2 and 3: maxProd = 6, minProd = 2, best = 6.nums23-240123iAt -2 we swap max and min first, then maxProd = -2 andminProd = -12; best stays 6.nums23-240123iAt 4 we start fresh: maxProd = 4, minProd = -48; bestis still 6.if num < 0: swap(maxProd, minProd)maxProd = max(num, maxProd * num)minProd = min(num, minProd * num)best = max(best, maxProd)
A negative number can turn the smallest product into the largest, so we carry both values forward.
ComplexityTime O(n)Space O(1)We scan the array once, keeping only two running values, so time is linear and extra memory is constant.

What Trips People Up in Real Interviews

1

Confusing this with maximum sum subarray. Products can flip sign — a negative times a negative becomes positive. You need to track both max and min.

2

Not tracking the minimum product. The minimum product at position i-1 can become the maximum at position i if nums[i] is negative.

3

Forgetting to swap max and min when nums[i] is negative. This handles the sign flip.

4

Not handling zeros. A zero resets both max and min to the current element.

5

Forgetting to initialize result with nums[0] instead of 0. If all products are negative, 0 would be wrong — the answer is the least negative single element.

Solution Code

O(n) time
def maxProduct(nums):
    result = max_prod = min_prod = nums[0]
    for num in nums[1:]:
        if num < 0:
            max_prod, min_prod = min_prod, max_prod
        max_prod = max(num, max_prod * num)
        min_prod = min(num, min_prod * num)
        result = max(result, max_prod)
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Maximum Product Subarray problem?

Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product. The answer is guaranteed to fit in a 32-bit integer.

How do you solve Maximum Product Subarray?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Maximum Product Subarray?

Maximum Product Subarray is asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart, LinkedIn. It is a medium difficulty problem.

What are common mistakes on Maximum Product Subarray?
  • Confusing this with maximum sum subarray. Products can flip sign — a negative times a negative becomes positive. You need to track both max and min.
  • Not tracking the minimum product. The minimum product at position i-1 can become the maximum at position i if `nums[i]` is negative.
  • Forgetting to swap max and min when `nums[i]` is negative. This handles the sign flip.
  • Not handling zeros. A zero resets both max and min to the current element.
  • Forgetting to initialize result with `nums[0]` instead of 0. If all products are negative, 0 would be wrong — the answer is the least negative single element.