LeetCode · #152

Maximum Product Subarray Solution

Given an integer array, find the contiguous subarray with the largest product and return that product.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #152

🏗️

Pattern

DP — 1D min/max tracking

Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product. The answer fits in a 32-bit integer.

Example

 Input: nums = [2,3,-2,4]
Output: 6 // Subarray [2,3] has the largest product = 6. 

Constraints

 • 1 ≤ nums.length ≤ 2 × 10⁴ • -10 ≤ nums[i] ≤ 10  ← product won't overflow int 

Section Two · Approach 1

Brute Force — O(n²)

Check every subarray: for each start index, extend the product to the right and track the global maximum. Two nested loops.

Why it works

Examining every contiguous subarray guarantees we find the maximum product. The inner loop multiplies incrementally, so each subarray product is computed in O(1) amortized.

Why we can do better

Problem: O(n²) is too slow for n = 20,000. The key insight: at each position, the maximum product ending here is determined by just the previous maximum and minimum products (because negatives flip signs). One pass, tracking two values, gives O(n).

Java — O(n²) all subarrays

 class Solution {
public int maxProduct(int[] nums) {
int result = nums[0];
for (int i = 0; i < nums.length; i++) {
int prod = 1;
for (int j = i; j < nums.length; j++) {
                prod *= nums[j];
                result = Math.max(result, prod);
            }
        }
return result;
    }
}

Python — O(n²) all subarrays

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

Metric	Value
Time	O(n²)
Space	O(1)

Section Three · Approach 2

Min/Max Tracking — O(n) time, O(1) space

At each index, track both the maximum and minimum product ending here. A negative number flips the max to min and vice versa. Update global max at each step.

💡 Mental model: Imagine tracking the most extreme hot and cold temperature streaks. On a "sign-flip day" (negative number), your hottest streak becomes your coldest and vice versa. You always carry both the current hottest and coldest, because tomorrow's negative times today's coldest could produce a new hottest. Each day you also consider starting fresh (just today's temperature alone) — this handles zeros and breaks in the streak.

Algorithm

Initialize curMax = curMin = result = nums[0].
For each nums[i] (from index 1): compute candidates = {nums[i], curMax*nums[i], curMin*nums[i]}.
curMax = max(candidates), curMin = min(candidates).
result = max(result, curMax).

🎯 When to recognize this pattern:

"Maximum/minimum product/result where negatives can flip the answer." The signal: multiplication with negative numbers.
Always track both extremes.
Unlike Kadane's for max sum (only track max), products require both because a very negative × negative = very positive.

Why include nums[i] alone as a candidate:

If curMax and curMin are both weakened by a zero earlier, restarting the subarray at the current element may be better.
This is equivalent to "start a new subarray here" — the same role as Kadane's max(nums[i], curMax + nums[i]).

Section Four · Trace

Visual Walkthrough

Trace for nums = [2, 3, -2, 4].

Max Product Subarray — Min/Max Tracking

Section Five · Implementation

Code — Java & Python

Java — Min/Max tracking

 class Solution {
public int maxProduct(int[] nums) {
int curMax = nums[0], curMin = nums[0], result = nums[0];
for (int i = 1; i < nums.length; i++) {
int n = nums[i];
int tmpMax = Math.max(n, Math.max(curMax * n, curMin * n));
            curMin = Math.min(n, Math.min(curMax * n, curMin * n));
            curMax = tmpMax; // use tmpMax so curMin uses old curMax
result = Math.max(result, curMax);
        }
return result;
    }
}

Python — Min/Max tracking

 class Solution:
def maxProduct(self, nums: list[int]) -> int:
        cur_max = cur_min = result = nums[0]
for n in nums[1:]:
            candidates = (n, cur_max * n, cur_min * n)
            cur_max, cur_min = max(candidates), min(candidates)
            result = max(result, cur_max)
return result

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force (all subarrays)	O(n²)	O(1)	Simple but slow
DP array (max[] + min[])	O(n)	O(n)	Stores arrays; unnecessary space
Min/Max tracking ← optimal	O(n)	O(1)	Two variables; handles negatives and zeros

Why Kadane's doesn't directly apply: Kadane's algorithm for max sum only tracks the running max because negatives always reduce the sum. With products, a large negative × another negative = large positive. Tracking only max would miss these cases. Tracking both max and min handles the sign-flip correctly.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single element	`[-3]`	Result is -3. Must not default to 0.
Contains zero	`[-2,0,-1]`	Zero resets both curMax and curMin. Best subarray is [0] → 0.
All negatives	`[-2,-3,-4]`	Best is (-2)×(-3)=6 or single -2. curMin×negative becomes curMax.
Two negatives	`[-2,-3]`	Product = 6. Both negatives multiply to positive.
Large positive run	`[2,3,4,5]`	curMax grows multiplicatively: 120. curMin stays positive but grows too.
Zero in the middle	`[2,0,3]`	Zero splits subarrays. Best is max(2, 0, 3) = 3.

⚠ Common Mistake: Not using a temp variable for curMax before computing curMin. If you update curMax = max(n, curMax*n, curMin*n) first, then curMin = min(n, curMax*n, curMin*n) uses the new curMax instead of the old one. In Java, save tmpMax first. In Python, compute both candidates from the old values before assigning.

← Back to DP — 1D problems

LearningTree

LC 152 · Maximum Product Subarray — Solution & Explanation | DSA Guide