Maximum Product Subarray

Difficulty: medium

Problem

Given an integer array `nums`, pick a non-empty run of adjacent elements whose product is as large as possible and return that product.

The tests are built so that the result always fits in a 32-bit integer.

**Key Challenge:** - Negative numbers can flip the sign of products - Zero resets the product to zero - We need to track both maximum and minimum products

Example

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The run [2, 3] multiplies to 6. Extending it to the full array gives -48 and the run [-2, 4] gives -8, so 6 is the best product.

Brute-force approach

Check every possible subarray, calculate its product, and track the maximum product found.

Steps

  1. For each starting index i (outer loop)
  2. For each ending index j >= i (inner loop)
  3. Calculate the product of subarray nums[i..j]
  4. Update maxProduct if current product is larger

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Nested loops make it O(n²) - slow for large arrays
  • Recalculates products from scratch for overlapping subarrays
  • Doesn't leverage the relationship between consecutive subarrays

Optimal approach

Key insight: At each position, the maximum product can come from: (1) current element alone, (2) previous max × current, or (3) previous min × current (if both are negative).

Track both maximum and minimum products ending at each position. A negative minimum can become maximum when multiplied by a negative number.

Steps

  1. Initialize maxSoFar, minSoFar, and result to nums[0]
  2. For each element from index 1:
  3. - Calculate tempMax = max(curr, maxSoFar × curr, minSoFar × curr)
  4. - Calculate minSoFar = min(curr, maxSoFar × curr, minSoFar × curr)
  5. - Update maxSoFar = tempMax
  6. - Update result = max(result, maxSoFar)
  7. Return result

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function maxProduct(nums):
    // Track both max and min (negatives can flip)
    maxSoFar = nums[0]
    minSoFar = nums[0]
    result = nums[0]
    
    for i from 1 to n-1:
        curr = nums[i]
        // Calculate candidates
        tempMax = max(curr, maxSoFar * curr, minSoFar * curr)
        minSoFar = min(curr, maxSoFar * curr, minSoFar * curr)
        maxSoFar = tempMax
        
        result = max(result, maxSoFar)
    
    return result

Hints

  • A negative × negative = positive, so track minimum too
  • When you see a negative, max and min might swap roles
  • Zero forces you to start fresh from the next element

Complexity questions

What is the time complexity of the brute force approach?

O(n²). The brute force uses nested loops: outer loop for start (n), inner loop for end (n), giving O(n × n) = O(n²).

What is the time complexity of the optimal approach?

O(n). The optimal approach makes a single pass through the array, visiting each element once: O(n).

Why do we need to track both maximum and minimum products?

Because negative × negative = positive, so min can become max. A very negative minimum multiplied by a negative number can produce a large positive maximum. That's the key insight!

Check your understanding of Maximum Product Subarray

For array [2, 3, -2, 4], what is the maximum product subarray?

6 (subarray [2, 3]). The subarray [2, 3] gives a product of 6. Including -2 would make it negative (-12), and the full array gives -48. So 6 is the maximum.

For array [-2, 3, -4], what is the maximum product subarray?

24. The entire array [-2, 3, -4] = (-2) × 3 × (-4) = 24. Two negatives make a positive!

Related problems

Keep practising