Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Maximum Product Subarray

MEDIUMProblemSolveExternal Links

Description

Given an integer array nums, find a contiguous subarray (containing at least one number) that has the largest product, and return that product.

The array can contain positive numbers, negative numbers, and zeros. A single element by itself counts as a valid subarray.

The key challenge is that negative numbers can flip the sign of a product: a very negative running product can suddenly become the largest positive product when multiplied by another negative number. This makes a simple greedy maximum-tracking approach insufficient — you must also consider how negative intermediate products can contribute to the final answer.

Examples

Example 1

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

Output: 6

Explanation: The subarray [2, 3] has the largest product: 2 × 3 = 6. Including -2 would make the product negative (-12), and extending further to include 4 gives -48. So the best contiguous subarray stops at index 1.

Example 2

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

Output: 0

Explanation: The maximum product is 0 (the subarray [0]). The subarray [-2, -1] is not valid because it's not contiguous — there is a 0 in between. [-2, 0, -1] gives product 0, and each element alone gives -2, 0, or -1.

Example 3

Input: nums = [-2, 6, -3, -10, 0, 2]

Output: 180

Explanation: The subarray [6, -3, -10] has the largest product: 6 × (-3) × (-10) = 180. Two negatives multiply to a positive, yielding a very large product. The 0 at index 4 prevents including more elements to the right.

Constraints

  • 1 ≤ nums.length ≤ 2 × 10^4
  • -10 ≤ nums[i] ≤ 10
  • The product of any subarray of nums is guaranteed to fit in a 32-bit integer

Editorial

Brute Force

Intuition

The most direct approach is to check every possible contiguous subarray, compute its product, and keep track of the maximum product seen.

A contiguous subarray is defined by its starting index i and ending index j (where i ≤ j). We can enumerate all subarrays by fixing a starting index, then expanding the end index one element at a time, multiplying as we go.

This is similar to the brute force for "Maximum Subarray Sum" (Kadane's problem), but with multiplication instead of addition. The key difference is that unlike sums, products can grow very quickly in magnitude — and a single negative number flips the sign of the entire running product.

For each starting index i, we maintain a running product. As we extend the subarray to include nums[j], we multiply the running product by nums[j] and compare with the global maximum.

Step-by-Step Explanation

Let's trace with nums = [2, 3, -2, 4]:

Step 1: Initialize maxProd = nums[0] = 2.

Step 2: Start from i = 0. Running product = 1.

  • j = 0: product = 1 × 2 = 2. maxProd = max(2, 2) = 2
  • j = 1: product = 2 × 3 = 6. maxProd = max(2, 6) = 6
  • j = 2: product = 6 × (-2) = -12. maxProd = max(6, -12) = 6
  • j = 3: product = -12 × 4 = -48. maxProd = max(6, -48) = 6

Step 3: Start from i = 1. Running product = 1.

  • j = 1: product = 3. maxProd = max(6, 3) = 6
  • j = 2: product = -6. maxProd = 6
  • j = 3: product = -24. maxProd = 6

Step 4: Start from i = 2. Running product = 1.

  • j = 2: product = -2. maxProd = 6
  • j = 3: product = -8. maxProd = 6

Step 5: Start from i = 3. Running product = 1.

  • j = 3: product = 4. maxProd = max(6, 4) = 6

Step 6: Return maxProd = 6. The maximum product subarray is [2, 3].

Brute Force — Check All Subarrays — Watch how we enumerate every contiguous subarray by fixing a start index and expanding the end index, tracking the running product and updating the global maximum.

Algorithm

  1. Initialize maxProd = nums[0]
  2. For each starting index i from 0 to n-1:
    • Set product = 1
    • For each ending index j from i to n-1:
      • Multiply: product *= nums[j]
      • Update: maxProd = max(maxProd, product)
  3. Return maxProd

Code

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int maxProd = nums[0];
        
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = i; j < n; j++) {
                product *= nums[j];
                maxProd = max(maxProd, product);
            }
        }
        return maxProd;
    }
};
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        max_prod = nums[0]
        
        for i in range(n):
            product = 1
            for j in range(i, n):
                product *= nums[j]
                max_prod = max(max_prod, product)
        
        return max_prod
class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxProd = nums[0];
        
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = i; j < n; j++) {
                product *= nums[j];
                maxProd = Math.max(maxProd, product);
            }
        }
        return maxProd;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times and the inner loop runs up to n times for each outer iteration. Total iterations: n(n+1)/2 ≈ O(n²).

Space Complexity: O(1)

We only use a few integer variables (product, maxProd). No additional data structures.

Why This Approach Is Not Efficient

With n up to 2 × 10^4, the brute force performs up to ~2 × 10^8 operations — this is borderline and may result in Time Limit Exceeded on strict judges.

The fundamental inefficiency is that we recompute overlapping products. When we extend a subarray from [i..j] to [i..j+1], we already know the product of [i..j] — we just need to multiply by nums[j+1]. But we throw that information away when we move to a new starting index.

Can we process each element just once and maintain enough information to determine the maximum product? The key insight is:

  • Unlike sums, where a negative running sum should be discarded (Kadane's), a very negative running product should be kept — because it might become the maximum when multiplied by the next negative number.

This means at each position, we need to track both the maximum product and the minimum product (most negative) ending at that position. This dual-tracking lets us handle sign flips in a single pass.

Optimal Approach - Track Max and Min Product

Intuition

This is a modified version of Kadane's algorithm, adapted for products instead of sums.

The key insight is that at every index, we maintain two values:

  • currMax: the maximum product of any subarray ending at this index
  • currMin: the minimum product of any subarray ending at this index

Why do we need the minimum? Because of negative numbers. A very small (negative) product × a negative number = a very large positive product. So the minimum product at position i can become the maximum product at position i+1.

At each step, we have three candidates for both the new max and new min:

  1. nums[i] alone (start a fresh subarray here)
  2. nums[i] × currMax (extend the previous max subarray)
  3. nums[i] × currMin (extend the previous min subarray — this handles the negative × negative case)

We pick the largest of the three for the new currMax, and the smallest for the new currMin. We update the global answer with currMax at each step.

What about zeros? When nums[i] = 0, all three candidates become 0 (since currMax × 0 = 0, currMin × 0 = 0, and nums[i] = 0). This effectively "resets" both currMax and currMin to 0, which is correct because any subarray containing 0 has product 0. The next iteration will start fresh.

Step-by-Step Explanation

Let's trace with nums = [2, 3, -2, 4]:

Step 1: Initialize currMax = 2, currMin = 2, maxProd = 2 (start with nums[0]).

Step 2: i = 1, nums[1] = 3.

  • Candidates: 3, 3×2=6, 3×2=6
  • New currMax = max(3, 6, 6) = 6
  • New currMin = min(3, 6, 6) = 3
  • maxProd = max(2, 6) = 6

Step 3: i = 2, nums[2] = -2.

  • Candidates: -2, -2×6=-12, -2×3=-6
  • New currMax = max(-2, -12, -6) = -2
  • New currMin = min(-2, -12, -6) = -12
  • maxProd = max(6, -2) = 6

Notice: currMin = -12 (the product [2,3,-2]). We keep this because if we encounter another negative number, -12 × negative = large positive!

Step 4: i = 3, nums[3] = 4.

  • Candidates: 4, 4×(-2)=-8, 4×(-12)=-48
  • New currMax = max(4, -8, -48) = 4
  • New currMin = min(4, -8, -48) = -48
  • maxProd = max(6, 4) = 6

Step 5: Return maxProd = 6.

Optimal — Dual Tracking (currMax / currMin) on [2, 3, -2, 4] — Watch how we maintain both the maximum and minimum product ending at each index. The minimum is kept because a negative × negative = positive, which could become the new maximum.

Now let's see the power of min-tracking with nums = [-2, 6, -3, -10, 0, 2]:

Optimal — Dual Tracking on [-2, 6, -3, -10, 0, 2] (Negative × Negative Power) — This example shows why tracking the minimum product is essential: the subarray [6, -3, -10] produces 180 because two negatives multiply to a large positive.

Algorithm

  1. Initialize currMax = nums[0], currMin = nums[0], maxProd = nums[0]
  2. For each index i from 1 to n-1:
    • Compute tempMax = max(nums[i], nums[i] × currMax, nums[i] × currMin)
    • Compute currMin = min(nums[i], nums[i] × currMax, nums[i] × currMin)
    • Set currMax = tempMax (use temp to avoid overwriting before currMin is computed)
    • Update maxProd = max(maxProd, currMax)
  3. Return maxProd

Important: We must compute tempMax before updating currMin, because currMin's calculation uses the old currMax value.

Code

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int currMax = nums[0];
        int currMin = nums[0];
        int maxProd = nums[0];
        
        for (int i = 1; i < n; i++) {
            int tempMax = max({nums[i], nums[i] * currMax, nums[i] * currMin});
            currMin = min({nums[i], nums[i] * currMax, nums[i] * currMin});
            currMax = tempMax;
            maxProd = max(maxProd, currMax);
        }
        return maxProd;
    }
};
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        curr_max = nums[0]
        curr_min = nums[0]
        max_prod = nums[0]
        
        for i in range(1, n):
            temp_max = max(nums[i], nums[i] * curr_max, nums[i] * curr_min)
            curr_min = min(nums[i], nums[i] * curr_max, nums[i] * curr_min)
            curr_max = temp_max
            max_prod = max(max_prod, curr_max)
        
        return max_prod
class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int currMax = nums[0];
        int currMin = nums[0];
        int maxProd = nums[0];
        
        for (int i = 1; i < n; i++) {
            int tempMax = Math.max(nums[i], Math.max(nums[i] * currMax, nums[i] * currMin));
            currMin = Math.min(nums[i], Math.min(nums[i] * currMax, nums[i] * currMin));
            currMax = tempMax;
            maxProd = Math.max(maxProd, currMax);
        }
        return maxProd;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array exactly once. At each index, we perform a constant number of comparisons and multiplications (computing max/min of three values). Total: O(n).

Space Complexity: O(1)

We use only three variables: currMax, currMin, and maxProd. No additional arrays or data structures needed, regardless of input size.