Maximum Product Subarray

Difficulty: medium

Problem

Given an integer array `nums`, find a contiguous 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.

**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 subarray [2, 3] has the largest product = 6. Although [2, 3, -2, 4] = -48, and [-2, 4] = -8, the best is [2, 3] = 6.

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)