3.17 Maximum Product Subarray

3.17.1 Problem Metadata

3.17.2 Description

Find the contiguous subarray within an array that has the largest product.

3.17.3 Examples

Input: [2,3,-2,4]
Output: 6 (subarray [2,3])

3.17.4 Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10

3.17.5 Solution - Track Max and Min Products

3.17.5.1 Walkthrough

This solution is a variant of Kadane’s algorithm (see Kadane’s Algorithm) adapted for products instead of sums. The key challenge is that negative numbers flip signs, making a large negative product potentially valuable if we later multiply by another negative.

Core Strategy:

Track two values at each position: - maxSoFar: Maximum product of subarray ending at current index - minSoFar: Minimum product of subarray ending at current index

Why track both max AND min?

Because negative numbers flip signs: - A large negative × negative = large positive - Today’s minimum could become tomorrow’s maximum

The Decision at Each Position (Kadane’s principle):

For each element num, we must decide: 1. Start fresh: Begin a new subarray from num 2. Extend: Multiply num with the previous max/min products

This gives us:

maxSoFar = max(num, num × previous_max, num × previous_min)
minSoFar = min(num, num × previous_max, num × previous_min)

The Swap Optimization:

When num < 0, multiplying by it flips signs: - previous_max × num becomes negative (likely the new minimum) - previous_min × num becomes positive (likely the new maximum)

By swapping max and min before multiplying, we simplify the logic:

if (num < 0) swap(maxSoFar, minSoFar)
maxSoFar = max(num, maxSoFar × num)
minSoFar = min(num, minSoFar × num)

Example Walkthrough:

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

i=0: num=2
  maxSoFar = 2, minSoFar = 2, answer = 2

i=1: num=3
  maxSoFar = max(3, 2×3) = 6
  minSoFar = min(3, 2×3) = 3
  answer = 6

i=2: num=-2 (negative → swap first!)
  After swap: maxSoFar=3, minSoFar=6
  maxSoFar = max(-2, 3×(-2)) = -2
  minSoFar = min(-2, 6×(-2)) = -12
  answer = 6

i=3: num=4
  maxSoFar = max(4, -2×4) = 4  ← Start fresh!
  minSoFar = min(4, -12×4) = -48
  answer = 6

Result: 6 (from subarray [2,3])

Key Insight: Just like Kadane’s algorithm for sums, we compare num (start fresh) vs extending the previous subarray. The difference is we track both extremes (max and min) because products can flip signs.

3.17.5.2 Analysis

  • Time Complexity: O(n)
    • Single pass through the array
    • Each iteration performs constant-time operations (comparisons, multiplications, swap)
    • No nested loops or recursion
  • Space Complexity: O(1)
    • Only uses three variables (maxSoFar, minSoFar, answer) regardless of input size
    • No additional data structures
    • This is optimal for the problem

Why This Approach is Optimal: - We must examine every element at least once → O(n) is the lower bound - We cannot do better than O(1) space while still tracking necessary state - The swap optimization elegantly handles negative numbers without complex branching

3.17.5.3 Implementation Steps

Initialization: 1. Set maxSoFar = nums[0] (maximum product ending at position 0) 2. Set minSoFar = nums[0] (minimum product ending at position 0) 3. Set answer = nums[0] (global maximum so far)

Main Loop (iterate from index 1 to n-1):

For each element num = nums[i]:

  1. Handle negative numbers (swap optimization):
    • If num < 0:
      • Save temp = maxSoFar
      • Set maxSoFar = minSoFar (min becomes max after multiplying by negative)
      • Set minSoFar = temp (max becomes min after multiplying by negative)
  2. Update maxSoFar (best product ending here):
    • Compare two choices:
      • Start fresh: num (begin new subarray from current element)
      • Extend: maxSoFar × num (multiply with previous best)
    • Set maxSoFar = Math.max(num, maxSoFar × num)
    • Why compare with num not maxSoFar? We need the option to restart the subarray, just like in Kadane’s algorithm!
  3. Update minSoFar (worst product ending here):
    • Set minSoFar = Math.min(num, minSoFar × num)
    • Track minimum for when we encounter another negative number
  4. Update global maximum:
    • Set answer = Math.max(answer, maxSoFar)
    • Only maxSoFar can contribute to the answer (we want maximum product)

Return:

  1. Return answer (the maximum product found across all subarrays)

3.17.5.4 Code - Java

public int maxProduct(int[] nums) {
    int maxSoFar = nums[0];
    int minSoFar = nums[0];
    int answer = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int num = nums[i];
        if (num < 0) {
            int temp = maxSoFar;
            maxSoFar = minSoFar;
            minSoFar = temp;
        }
        maxSoFar = Math.max(num, maxSoFar * num);
        minSoFar = Math.min(num, minSoFar * num);
        answer = Math.max(answer, maxSoFar);
    }

    return answer;
}