Maximum Product Subarray

Medium

💭 Introduction

You’re given an array of integers (which can be positive, negative, or zero). Your task is to find the contiguous subarray with the largest product.

Unlike the sum version, products behave differently with negative numbers!

A negative number multiplied by another negative becomes positive. This twist makes the problem more interesting and challenging.

Your goal is to find which contiguous subarray has the maximum product.

🧩 Problem Statement

LeetCode #152 — Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray within the array 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.

🔍 Example 1: 

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

Explanation:

The subarray [2,3] has the largest product = 6.

🔍 Example 2: 

Input: nums = [-2,0,-1]
Output: 0

Explanation:

The result cannot be 2, because [-2,-1] is not a subarray. The maximum product is 0 from the subarray [0].

🔍 Example 3: 

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

Explanation:

The subarray [-2,3,-4] has the largest product = 24. Notice how two negatives make a positive!

🧠 Step 1: Why Maximum Subarray Approach Fails

You might think: “Just use Kadane’s Algorithm but with multiplication!”

# This DOESN'T work!
def maxProduct(nums):
    max_prod = current_prod = nums[0]
    
    for num in nums[1:]:
        current_prod = max(num, current_prod * num)
        max_prod = max(max_prod, current_prod)
    
    return max_prod

Why does this fail?

Consider nums = [2, -5, -2]:

  • At index 1: current_prod = max(-5, 2 * -5) = -5
  • At index 2: current_prod = max(-2, -5 * -2) = 10 ✓

But consider nums = [-2, 3, -4]:

  • At index 1: current_prod = max(3, -2 * 3) = 3
  • At index 2: current_prod = max(-4, 3 * -4) = -4 ✗

We missed the answer 24 because we lost track of the negative product -6 at index 1!

🤔 Step 2: The Key Insight

Here’s the crucial observation:

A negative number can turn a small negative product into a large positive product!

We need to track both:

  1. Maximum product ending at current position
  2. Minimum product ending at current position (which might become maximum later!)

Why track minimum?

  • A large negative number (minimum) × negative number = large positive (maximum)
  • Example: -10 × -5 = 50

🚀 Step 3: The Two-Tracker Solution

At each position, we maintain:

  • max_prod: maximum product ending here
  • min_prod: minimum product ending here

For each new number, we have three choices:

  1. Start fresh with just the current number
  2. Multiply with previous maximum
  3. Multiply with previous minimum (important for negatives!)
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        max_prod = min_prod = result = nums[0]
        
        for num in nums[1:]:
            # When we multiply by negative, max becomes min and vice versa
            if num < 0:
                max_prod, min_prod = min_prod, max_prod
            
            # Update max and min products
            max_prod = max(num, max_prod * num)
            min_prod = min(num, min_prod * num)
            
            # Update global result
            result = max(result, max_prod)
        
        return result

Let’s trace through Example 3: [-2, 3, -4]

i num Before swap After swap max_prod min_prod result
0 -2 - - -2 -2 -2
1 3 max=-2, min=-2 (no swap) max(3, -2×3)=3 min(3, -2×3)=-6 3
2 -4 max=3, min=-6 max=-6, min=3 max(-4, -6×-4)=24 min(-4, 3×-4)=-12 24

Final answer: 24

⏱️ Time Complexity: $O(n)$ — Single pass through the array

📦 Space Complexity: $O(1)$ — Only a few variables

🎯 Step 4: Alternative Formulation (Without Swap)

We can avoid the swap by computing both possibilities at once:

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        max_prod = min_prod = result = nums[0]
        
        for num in nums[1:]:
            # Store previous values
            temp_max = max_prod
            
            # Compute new max and min considering all possibilities
            max_prod = max(num, max_prod * num, min_prod * num)
            min_prod = min(num, temp_max * num, min_prod * num)
            
            result = max(result, max_prod)
        
        return result

This version is clearer and doesn’t require the swap trick.

🧮 Step 5: Understanding as Dynamic Programming

Let’s formalize this as DP:

Define:

  • max_dp[i] = maximum product of subarray ending at index i
  • min_dp[i] = minimum product of subarray ending at index i

Recurrence relation:

max_dp[i] = max(nums[i], max_dp[i-1] * nums[i], min_dp[i-1] * nums[i])
min_dp[i] = min(nums[i], max_dp[i-1] * nums[i], min_dp[i-1] * nums[i])

Base case:

max_dp[0] = nums[0]
min_dp[0] = nums[0]

Answer:

max(max_dp[0], max_dp[1], ..., max_dp[n-1])

Here’s the explicit DP version:

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

⏱️ Time: $O(n)$

📦 Space: $O(n)$

🔄 Step 6: Handling Zero

Zero is a special case — it resets everything:

  • Any product with 0 becomes 0
  • It acts as a natural “restart point”

Our algorithm handles this naturally:

max_prod = max(num, max_prod * num, min_prod * num)

When num = 0:

  • max_prod = max(0, max_prod * 0, min_prod * 0) = 0
  • Effectively starts fresh from the next element

🎯 Key Insights

  1. Track both extremes: Unlike sum, we need both maximum and minimum products.

  2. Negative numbers flip: A negative number can turn minimum into maximum.

  3. Three choices: At each position, consider starting fresh, extending max, or extending min.

  4. Zero resets: Zero naturally acts as a divider between subarrays.

  5. Even negatives: An even number of negatives gives a positive product.

📊 Complexity Summary

Approach Time Space
Brute Force $O(n^2)$ or $O(n^3)$ $O(1)$
DP with Arrays $O(n)$ $O(n)$
Space Optimized $O(n)$ $O(1)$

🌟 Edge Cases to Consider

  1. All negative numbers: [-2, -3, -4] → Answer: 3 (single element)
  2. Contains zero: [2, 0, -3] → Answer: 2
  3. Single element: [5] → Answer: 5
  4. Two negatives: [-2, -3] → Answer: 6
  5. Alternating signs: [2, -5, -2, -4, 3] → Answer: 24

💡 Common Mistakes

  1. Forgetting minimum tracker: Only tracking maximum misses negative × negative = positive
  2. Not handling zero: Zero should reset the product chain
  3. Wrong swap logic: Swapping at wrong time or not considering all three options
  4. Integer overflow: For very large products (though problem guarantees 32-bit fit)

🔍 Comparison with Maximum Subarray

Aspect Maximum Sum Maximum Product
Negative impact Always decreases Can increase (neg × neg)
Trackers needed 1 (max) 2 (max and min)
Zero handling Neutral Resets to 0
Complexity Simpler More complex

💡 Related Problems

  • Maximum Subarray - The sum version
  • House Robber - Similar DP pattern
  • Maximum Product of Three Numbers - Related product problem
  • Best Time to Buy and Sell Stock - Similar optimization pattern

🏆 Why This Problem Matters

  1. Interview favorite: Tests understanding of DP and edge cases
  2. Negative number handling: Teaches how signs affect optimization
  3. State tracking: Shows when you need multiple states
  4. Real-world applications: Financial calculations, optimization problems