Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 152. Maximum Product Subarray

Find the contiguous subarray with the largest product in an integer array; because negatives and zeros can flip signs, you must track both the running maximum and minimum products at each step to correctly handle sign changes.

Asked at:

Microsoft

DESCRIPTION

Input:

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

Output:

Explanation: The subarray [2,3] has the largest product of 6

Constraints:

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer
Array contains at least one element

Understanding the Problem

Let's understand what we're being asked to do. We have an array like [2, 3, -2, 4] and need to find the contiguous subarray with the largest product.

Tracing through: [2] has product 2, [2,3] has product 6, [2,3,-2] has product -12, [2,3,-2,4] has product -48. But wait - what about [3,-2,4]? That's -24. And [-2,4]? That's -8. Actually, the subarray [2,3] gives us the maximum product of 6.

Critical insight: Unlike sum problems, negative numbers can flip signs! A negative number multiplied by another negative becomes positive. So we can't just track one running product - we need to track BOTH the maximum AND minimum products at each position.

Why track minimum? Consider [2, -5, -3]. At index 1, the minimum product is -10. When we see -3 at index 2, that minimum -10 becomes 30 (a maximum!). The negative minimum can become a positive maximum when multiplied by another negative.

Edge cases to consider: What if the array contains zeros? (zeros reset the product). What if all numbers are negative? What if there's only one element?

Brute Force Approach

The brute force approach checks every possible contiguous subarray by using nested loops. For each starting position, we iterate through all possible ending positions, calculating the product of elements in that range. We keep track of the maximum product seen across all subarrays. This approach is straightforward but inefficient because it recalculates products from scratch for overlapping subarrays.

Visualization

def max_product_subarray(nums):
    """
    Find the contiguous subarray with the largest product.
    Uses brute force approach checking all possible subarrays.
    """
    if not nums:
        return 0
    
    max_product = nums[0]
    n = len(nums)
    
    # Try every possible starting position
    for i in range(n):
        current_product = 1
        
        # Try every possible ending position from current start
        for j in range(i, n):
            # Multiply current element into the product
            current_product *= nums[j]
            
            # Update maximum if current product is larger
            max_product = max(max_product, current_product)
    
    return max_product

Start brute force: check all subarrays

0 / 45

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) We use nested loops to check all possible subarrays. For each of n starting positions, we check up to n ending positions, resulting in quadratic time complexity

Space Complexity: O(1) We only use a constant amount of extra space to track the current product and maximum product

Building Intuition

At each position, we need to track TWO values: the maximum product ending here AND the minimum product ending here.

Why? Because a negative number can flip signs. A large negative product (minimum) becomes a large positive product when multiplied by another negative number. Similarly, a large positive product (maximum) becomes a large negative when multiplied by a negative.

This is fundamentally different from maximum subarray sum problems. With sums, we only track the maximum because adding a negative just makes it smaller.

But with products, negatives can become positives through multiplication. The minimum product at one step might become the maximum product at the next step if we encounter another negative number. We must track both extremes!

Think about walking through [2, -5, -3] step by step:

At 2: max=2, min=2
At -5: max=-5 (starting fresh), min=-10 (continuing from 2)
At -3: max=30 (the min -10 flipped positive!), min=15 (the max -5 became less negative)

The key is that at each number, we consider THREE choices: start fresh with just this number, extend the maximum product, or extend the minimum product. We keep both extremes because either could become the answer later.

Common Mistakes

Only tracking the maximum product without tracking minimum - this fails when two negatives multiply to create a large positive

Forgetting to consider starting fresh at each position - the current element alone might be larger than any product involving previous elements

Not handling zeros correctly - zeros should reset both max and min products, not propagate through calculations

Confusing this with maximum subarray sum - the logic is fundamentally different because multiplication has different properties than addition

Integer overflow concerns - forgetting that products can grow very large, though the problem guarantees they fit in 32-bit integers

Optimal Solution

The optimal approach uses dynamic programming to track both the maximum and minimum products ending at each position. At each element, we calculate three candidates: the element itself (starting fresh), the element multiplied by the previous maximum (extending positive), and the element multiplied by the previous minimum (which could flip to positive if both are negative). We update both max and min products, then track the global maximum. This handles sign flips elegantly in a single pass.

Visualization

def max_product_subarray(nums):
    """
    Find the contiguous subarray with the largest product.
    Track both max and min products to handle negative numbers.
    """
    if not nums:
        return 0
    
    # Initialize with first element
    global_max = nums[0]
    current_max = nums[0]
    current_min = nums[0]
    
    # Iterate through remaining elements
    for i in range(1, len(nums)):
        num = nums[i]
        
        # Calculate three candidates
        temp_max = current_max
        candidate1 = num
        candidate2 = num * temp_max
        candidate3 = num * current_min
        
        # Update current max and min
        current_max = max(candidate1, candidate2, candidate3)
        current_min = min(candidate1, candidate2, candidate3)
        
        # Update global maximum
        global_max = max(global_max, current_max)
    
    return global_max

Start finding maximum product subarray

0 / 14

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We iterate through the array once, performing constant-time calculations at each position to update max and min products

Space Complexity: O(1) We only need two variables to track the current maximum and minimum products, regardless of array size

What We've Learned

Dual-state dynamic programming: When dealing with sign-changing operations (multiplication with negatives), track both maximum and minimum products simultaneously - today's minimum can become tomorrow's maximum when multiplied by a negative number, making this dual-tracking essential for correctness.
State transition with sign awareness: At each position, calculate three candidates: current number alone (starting fresh), max_so_far × current, and min_so_far × current - this handles the case where a large negative number or zero makes it better to restart the subarray rather than continue.
Space-optimized rolling variables: Use O(1) space by maintaining only `max_ending_here` and `min_ending_here` instead of full DP arrays - since each position only depends on the previous position's values, you can overwrite as you go, making this a constant-space solution.
Zero-handling edge case: Zeros reset both max and min products to zero, effectively breaking the subarray - ensure your logic naturally handles this by including the current number itself as a candidate (max/min of current alone), which allows the algorithm to restart after encountering zeros.
Modified Kadane's algorithm pattern: This extends Kadane's maximum subarray technique to multiplicative problems - whenever you have operations that can flip optimality (negatives in multiplication, division, XOR), consider tracking both extremes (max/min) rather than just the maximum.
Financial portfolio optimization: This pattern applies to compound growth scenarios where negative returns can flip - tracking best and worst case scenarios simultaneously is crucial in risk analysis, investment strategies, and any domain where multiplicative effects and sign changes interact.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid November, 2025

Mid-level

Follow up 152

Mid November, 2025

Microsoft

Mid-level

Given an integer array nums, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer. Note that the product of an array with a single element is the value of that element.

Early November, 2025

Mid-level

Get Premium to View All 7 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 152. Maximum Product Subarray

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact