Maximum Product Subarray

Problem

Given an integer array nums, return the largest product of any contiguous non-empty subarray.

Intuition

The obvious first attempt — track only max_ending_here — breaks immediately. Walk [-2, 3, -4]:

• After -2: best ending here is -2. (It's the only option.)
• After 3: best ending here is 3. (Starting fresh beats -6.)
• After -4: best ending here is -4. (3 * -4 = -12 is worse.)

We return 3. Wrong — the right answer is 24.

The fix is that today's min can become tomorrow's max when tomorrow's element is negative. A very negative product, multiplied by another negative, flips to a large positive. So we have to carry both extremes forward:

new_max = max(x, prev_max * x, prev_min * x)
new_min = min(x, prev_max * x, prev_min * x)

Every transition considers three options: extend the max, extend the min, or start fresh at the current element (resetting both). The global answer is the max we've ever seen for max_ending_here across the whole walk.

This is the same "two rolling scalars" shape as #198, with one twist: we roll two different quantities, and their roles can swap on a negative number.

Approach

impl Solution {
    pub fn max_product(nums: Vec<i32>) -> i32 {
        let mut best = nums[0];
        for i in 0..nums.len() {
            let mut prod: i32 = 1;
            for j in i..nums.len() {
                prod = prod.saturating_mul(nums[j]);
                best = best.max(prod);
            }
        }
        best
    }
}

function maxProduct(nums: number[]): number {
  let best = nums[0];
  for (let i = 0; i < nums.length; i++) {
    let prod = 1;
    for (let j = i; j < nums.length; j++) {
      prod *= nums[j];
      best = Math.max(best, prod);
    }
  }
  return best;
}

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        best = nums[0]
        for i in range(len(nums)):
            prod = 1
            for j in range(i, len(nums)):
                prod *= nums[j]
                best = max(best, prod)
        return best

impl Solution {
    pub fn max_product(nums: Vec<i32>) -> i32 {
        let mut curr_max = nums[0];
        let mut curr_min = nums[0];
        let mut best = nums[0];
        for &x in &nums[1..] {
            let prev_max = curr_max;
            curr_max = x.max(prev_max * x).max(curr_min * x);
            curr_min = x.min(prev_max * x).min(curr_min * x);
            best = best.max(curr_max);
        }
        best
    }
}

function maxProduct(nums: number[]): number {
  let currMax = nums[0];
  let currMin = nums[0];
  let best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const x = nums[i];
    const prevMax = currMax;
    currMax = Math.max(x, prevMax * x, currMin * x);
    currMin = Math.min(x, prevMax * x, currMin * x);
    best = Math.max(best, currMax);
  }
  return best;
}

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        curr_max = curr_min = best = nums[0]
        for x in nums[1:]:
            candidates = (x, curr_max * x, curr_min * x)
            curr_max, curr_min = max(candidates), min(candidates)
            best = max(best, curr_max)
        return best

Trace

Rolling pair on nums = [2, 3, -2, 4]:

best = 6. ✓ Note how index 2 flipped the roles: what was the biggest product (6) became the most-negative candidate once multiplied by -2.

Edge cases

• Single element — return nums[0]. The loop doesn't execute; best is seeded correctly.
• Contains zero — zero resets both rolling values (since x alone beats prev_* * 0). That's correct: a subarray crossing a zero is zero.
• All negatives, odd count — some single element is the answer. Example: [-3, -1, -2] → 6 (subarray [-3, -1], [-1, -2], or [-3, -1, -2] gives -6 — wait, actually that's (-3)*(-1) = 3, (-1)*(-2) = 2, and the whole is -6, so best is 3). The rolling pair handles this without special casing.
• Integer overflow — LeetCode caps the product at i32::MAX. The brute form uses saturating_mul to avoid undefined-behavior panics; the rolling form can't overflow in practice because a negative product would immediately beat a positive one on the next negative.

Takeaway

When a rolling-DP looks like it should work but fails on signs, the usual fix is to roll both extremes. #152 is the canonical example. It's the same skeleton as #198 (state = best value ending at i, transition = small choice), but the non-monotonicity of multiplication forces you to double the state.

This reflex carries forward: whenever an operation can flip extremes, you carry both. Interval DP over trees (see #337 House Robber III) uses the same trick with a (rob, skip) pair per node — rooting choices can flip which option dominates.