212. Maximum Product Subarray
🔗 LeetCode Problem: 152. Maximum Product Subarray
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Array, 1D DP
Problem Statement
Given an integer array nums, find a 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.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
🌳 Visual Understanding - Using [2, 3, -2, 4]
The Problem We're Solving:
Given: nums = [2, 3, -2, 4]
Goal: Find the subarray with maximum product
Subarray: Must be continuous elements!
[2, 3] ✓
[2, 3, -2] ✓
[2, 4] ✗ (not continuous - skipped 3 and -2)
Question: Which continuous subarray has the biggest product? 🤔
Finding All Subarrays for [2, 3, -2, 4]:
Array: [2, 3, -2, 4]
Starting at index 0 (value 2):
━━━━━━━━━━━━━━━━━━━━━━━━━━━
[2] → product = 2
[2, 3] → product = 6 ✓ MAXIMUM!
[2, 3, -2] → product = -12
[2, 3, -2, 4] → product = -48
Starting at index 1 (value 3):
━━━━━━━━━━━━━━━━━━━━━━━━━━━
[3] → product = 3
[3, -2] → product = -6
[3, -2, 4] → product = -24
Starting at index 2 (value -2):
━━━━━━━━━━━━━━━━━━━━━━━━━━━
[-2] → product = -2
[-2, 4] → product = -8
Starting at index 3 (value 4):
━━━━━━━━━━━━━━━━━━━━━━━━━━━
[4] → product = 4
All products: 2, 6, -12, -48, 3, -6, -24, -2, -8, 4
Maximum: 6 (from subarray [2, 3])
Answer: 6 ✓
Why This Is Tricky - The Negative Number Problem:
Consider: [2, -3, -4]
Subarray [2]:
Product = 2
Subarray [2, -3]:
Product = -6 (negative makes it small!)
Subarray [2, -3, -4]:
Product = 24 (two negatives = positive! BIG!) ✓
KEY INSIGHT:
Negative numbers can flip things!
Small negative × Small negative = BIG positive!
We can't just throw away negative products
because they might become big later! 🎯
Another Tricky Example - With Zero:
Array: [-2, 3, -4]
Without zero:
[-2] → -2
[-2, 3] → -6
[-2, 3, -4] → 24 ✓ (maximum!)
Now with zero: [-2, 0, 3, -4]
Subarrays:
[-2] → -2
[-2, 0] → 0 (zero kills the product!)
[-2, 0, 3] → 0
[-2, 0, 3, -4] → 0
[0] → 0
[0, 3] → 0
[0, 3, -4] → 0
[3] → 3 ✓ (best we can do!)
[3, -4] → -12
[-4] → -4
Maximum: 3 (zero breaks the chain!)
KEY INSIGHT:
Zero resets everything!
Products before zero can't connect to products after!
Must restart calculation after each zero! 🎯
🧠 The AHA Moment - Why This Problem Is Special
What Makes This Different from Maximum Sum Subarray?
MAXIMUM SUM (Kadane's Algorithm):
nums = [2, 3, -2, 4]
At each position, decide:
- Include current element in sum
- Start fresh from current element
Always prefer larger sum
Simple choice! ✓
MAXIMUM PRODUCT (This Problem):
nums = [2, 3, -2, 4]
At each position:
- Current product could be POSITIVE or NEGATIVE
- Negative × Negative = POSITIVE (might be useful!)
- Can't just keep maximum - need to track minimum too!
Must track BOTH max and min products! 🎯
The Key Insight - Track Two Values!
Why we need BOTH maximum AND minimum:
Example: [2, 3, -2, 4]
At position 0 (value 2):
max = 2
min = 2
At position 1 (value 3):
max = max(3, 2×3) = 6
min = min(3, 2×3) = 3
At position 2 (value -2):
max = max(-2, 6×(-2), 3×(-2)) = -2
min = min(-2, 6×(-2), 3×(-2)) = -12
Notice: min = -12 is VERY negative
This might become VERY positive later!
At position 3 (value 4):
We have:
- Previous max = -2
- Previous min = -12 (very negative!)
New candidates:
- Just 4: 4
- max × 4 = -2 × 4 = -8
- min × 4 = -12 × 4 = -48 (still negative)
max = max(4, -8, -48) = 4
min = min(4, -8, -48) = -48
Global maximum = 6 (found at position 1)
The minimum value at each step is like a "backup"
that might flip to become maximum later! 🎯
Better Example to Show Power of Negatives:
Array: [2, -5, -3]
Position 0 (value 2):
max = 2
min = 2
Position 1 (value -5):
Candidates:
- Just -5: -5
- max × -5 = 2 × -5 = -10
- min × -5 = 2 × -5 = -10
max = max(-5, -10) = -5
min = min(-5, -10) = -10 ← Keep this negative!
Position 2 (value -3):
Candidates:
- Just -3: -3
- max × -3 = -5 × -3 = 15
- min × -3 = -10 × -3 = 30 ← Negative flipped to POSITIVE! ✓
max = max(-3, 15, 30) = 30 ✓ MAXIMUM!
min = min(-3, 15, 30) = -3
The minimum -10 became maximum 30!
This is why we MUST track both! 🎯
🔴 Approach 1: Brute Force (Try All Subarrays)
📐 Function Definition
Function Signature:
int maxProduct(int[] nums)
What it represents:
Input Parameter nums:
- Array of integers (can be positive, negative, or zero)
- Example: nums = [2, 3, -2, 4]
Return Value (int): - Maximum product of any continuous subarray - Example: 6 (from subarray [2, 3])
Purpose: - Try every possible continuous subarray - Calculate product for each - Return the maximum product found
Key Understanding:
For [2, 3, -2, 4], we try:
Start 0: [2], [2,3], [2,3,-2], [2,3,-2,4]
Start 1: [3], [3,-2], [3,-2,4]
Start 2: [-2], [-2,4]
Start 3: [4]
Calculate product for each, return maximum!
💡 Intuition
The simplest idea: Just try everything!
Think of it like checking all possible slices of a loaf of bread:
Array: [2, 3, -2, 4]
Slices starting at position 0:
Slice 1 piece: [2] → product = 2
Slice 2 pieces: [2, 3] → product = 6 ✓
Slice 3 pieces: [2, 3, -2] → product = -12
Slice 4 pieces: [2, 3, -2, 4] → product = -48
Slices starting at position 1:
Slice 1 piece: [3] → product = 3
Slice 2 pieces: [3, -2] → product = -6
Slice 3 pieces: [3, -2, 4] → product = -24
Slices starting at position 2:
Slice 1 piece: [-2] → product = -2
Slice 2 pieces: [-2, 4] → product = -8
Slices starting at position 3:
Slice 1 piece: [4] → product = 4
Check all slices, remember the biggest product!
Maximum = 6 from [2, 3] ✓
Simple but slow for large arrays!
📝 Implementation
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int maxProduct = Integer.MIN_VALUE;
// Try all possible starting positions
for (int start = 0; start < n; start++) {
int product = 1;
// Try all possible ending positions from this start
for (int end = start; end < n; end++) {
product *= nums[end];
maxProduct = Math.max(maxProduct, product);
}
}
return maxProduct;
}
}
🔍 Detailed Dry Run: nums = [2, 3, -2, 4]
n = 4
maxProduct = -∞ (start with very small value)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
OUTER LOOP: Start at each position
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 1: start = 0
━━━━━━━━━━━━━━━━━━━━
product = 1
Inner loop (end = 0 to 3):
end = 0: nums[0] = 2
product = 1 × 2 = 2
maxProduct = max(-∞, 2) = 2
end = 1: nums[1] = 3
product = 2 × 3 = 6
maxProduct = max(2, 6) = 6 ✓
end = 2: nums[2] = -2
product = 6 × -2 = -12
maxProduct = max(6, -12) = 6
end = 3: nums[3] = 4
product = -12 × 4 = -48
maxProduct = max(6, -48) = 6
Iteration 2: start = 1
━━━━━━━━━━━━━━━━━━━━
product = 1
Inner loop (end = 1 to 3):
end = 1: nums[1] = 3
product = 1 × 3 = 3
maxProduct = max(6, 3) = 6
end = 2: nums[2] = -2
product = 3 × -2 = -6
maxProduct = max(6, -6) = 6
end = 3: nums[3] = 4
product = -6 × 4 = -24
maxProduct = max(6, -24) = 6
Iteration 3: start = 2
━━━━━━━━━━━━━━━━━━━━
product = 1
Inner loop (end = 2 to 3):
end = 2: nums[2] = -2
product = 1 × -2 = -2
maxProduct = max(6, -2) = 6
end = 3: nums[3] = 4
product = -2 × 4 = -8
maxProduct = max(6, -8) = 6
Iteration 4: start = 3
━━━━━━━━━━━━━━━━━━━━
product = 1
Inner loop (end = 3):
end = 3: nums[3] = 4
product = 1 × 4 = 4
maxProduct = max(6, 4) = 6
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: maxProduct = 6 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
The maximum product 6 came from subarray [2, 3]
Found during start=0, end=1
📊 Complexity Analysis
Time Complexity: O(n²)
Outer loop: n iterations (all starting positions)
Inner loop: up to n iterations (all ending positions)
Total: n × n = O(n²)
For n = 10,000: 100,000,000 operations
TOO SLOW for large arrays! ❌
Space Complexity: O(1)
Only using a few variables
No extra arrays needed
Why This Is Slow:
❌ Tries every possible subarray
❌ Too many operations for large n
❌ Can't use for n = 20,000
✅ But correct and easy to understand!
🟡 Approach 2: Dynamic Programming (Track Max and Min)
📐 Function Definition
Function Signature:
int maxProduct(int[] nums)
What it represents:
Variables we track:
- maxSoFar = Maximum product of subarray ending at current position
- minSoFar = Minimum product of subarray ending at current position
- result = Global maximum product found so far
Purpose: - At each position, calculate max and min products ending here - Use previous max/min to calculate current max/min - Track global maximum throughout
Key Understanding:
At each position i:
maxSoFar = maximum product of subarray ENDING at i
minSoFar = minimum product of subarray ENDING at i
Why ENDING at i?
We build up the solution as we go!
Example: [2, 3, -2, 4]
At i=0: max=2, min=2 (just [2])
At i=1: max=6, min=3 (best subarray ending at index 1)
At i=2: max=-2, min=-12 (best subarray ending at index 2)
At i=3: max=4, min=-48 (best subarray ending at index 3)
💡 Intuition
The clever idea: Keep track of BOTH the biggest and smallest products!
Think of it like tracking your bank account:
NORMAL THINKING (Maximum Sum):
"I only care about my maximum balance"
→ Only track the highest value
PRODUCT THINKING (This Problem):
"A huge negative debt × negative = huge positive profit!"
→ Must track BOTH highest AND lowest!
Example with money analogy:
You have: $2 (balance)
Day 1: Multiply by 3
Best: $2 × 3 = $6 ✓
Worst: $2 × 3 = $6
Day 2: Multiply by -2 (debt!)
Best: $6 × -2 = -$12 (now in debt)
Worst: $6 × -2 = -$12 (huge debt!)
Day 3: Multiply by -3 (more debt!)
Best: -$12 × -3 = $36 ✓ (debt × debt = profit!)
Worst: -$12 × -3 = $36
The "worst" debt became the "best" profit!
This is why we track both! 🎯
The Three Choices at Each Step:
At position i, we can:
1. Start fresh (just take current number)
→ Use when previous products are terrible
2. Extend the maximum product
→ maxSoFar × nums[i]
3. Extend the minimum product
→ minSoFar × nums[i] (might flip to huge positive!)
Choose the best for max, choose the worst for min!
Example: [2, 3, -2, 4]
At i=2 (value -2):
Previous: maxSoFar=6, minSoFar=3
Three choices for max:
1. Start fresh: -2
2. Extend max: 6 × -2 = -12
3. Extend min: 3 × -2 = -6
maxSoFar = max(-2, -12, -6) = -2 ✓
Three choices for min:
1. Start fresh: -2
2. Extend max: 6 × -2 = -12
3. Extend min: 3 × -2 = -6
minSoFar = min(-2, -12, -6) = -12 ✓
Keep the -12 because it might flip later!
📝 Implementation
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) return 0;
// Track maximum and minimum products ending at current position
int maxSoFar = nums[0];
int minSoFar = nums[0];
int result = nums[0];
// Process each element starting from index 1
for (int i = 1; i < nums.length; i++) {
int curr = nums[i];
// When we multiply by negative, max becomes min and min becomes max
// So we need to consider all three options
int tempMax = Math.max(curr, Math.max(maxSoFar * curr, minSoFar * curr));
int tempMin = Math.min(curr, Math.min(maxSoFar * curr, minSoFar * curr));
// Update max and min for next iteration
maxSoFar = tempMax;
minSoFar = tempMin;
// Update global maximum
result = Math.max(result, maxSoFar);
}
return result;
}
}
🔍 Detailed Dry Run: nums = [2, 3, -2, 4]
nums = [2, 3, -2, 4]
n = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
maxSoFar = nums[0] = 2
minSoFar = nums[0] = 2
result = nums[0] = 2
State: max=2, min=2, result=2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION - Process each element
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 1: i = 1, curr = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Previous state: maxSoFar=2, minSoFar=2
Three candidates for max:
1. Just curr: 3
2. maxSoFar × curr: 2 × 3 = 6 ✓
3. minSoFar × curr: 2 × 3 = 6
tempMax = max(3, 6, 6) = 6 ✓
Three candidates for min:
1. Just curr: 3
2. maxSoFar × curr: 2 × 3 = 6
3. minSoFar × curr: 2 × 3 = 6
tempMin = min(3, 6, 6) = 3 ✓
Update:
maxSoFar = 6
minSoFar = 3
result = max(2, 6) = 6 ✓
State: max=6, min=3, result=6
Iteration 2: i = 2, curr = -2
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Previous state: maxSoFar=6, minSoFar=3
Three candidates for max:
1. Just curr: -2 ✓
2. maxSoFar × curr: 6 × -2 = -12
3. minSoFar × curr: 3 × -2 = -6
tempMax = max(-2, -12, -6) = -2 ✓
Three candidates for min:
1. Just curr: -2
2. maxSoFar × curr: 6 × -2 = -12 ✓
3. minSoFar × curr: 3 × -2 = -6
tempMin = min(-2, -12, -6) = -12 ✓
Update:
maxSoFar = -2
minSoFar = -12 ← Keep this big negative!
result = max(6, -2) = 6
State: max=-2, min=-12, result=6
Iteration 3: i = 3, curr = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Previous state: maxSoFar=-2, minSoFar=-12
Three candidates for max:
1. Just curr: 4 ✓
2. maxSoFar × curr: -2 × 4 = -8
3. minSoFar × curr: -12 × 4 = -48
tempMax = max(4, -8, -48) = 4 ✓
Three candidates for min:
1. Just curr: 4
2. maxSoFar × curr: -2 × 4 = -8
3. minSoFar × curr: -12 × 4 = -48 ✓
tempMin = min(4, -8, -48) = -48 ✓
Update:
maxSoFar = 4
minSoFar = -48
result = max(6, 4) = 6
State: max=4, min=-48, result=6
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL RESULT: 6 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
The maximum product 6 was found at iteration 1
Corresponds to subarray [2, 3]
Key insight: We kept tracking minSoFar even when negative
because it could potentially flip to positive later!
Why This Works - Visual Table:
Position │ Value │ maxSoFar │ minSoFar │ result │ Explanation
─────────┼───────┼──────────┼──────────┼────────┼─────────────────────
0 │ 2 │ 2 │ 2 │ 2 │ Initial state
1 │ 3 │ 6 │ 3 │ 6 │ 2×3=6 is best ✓
2 │ -2 │ -2 │ -12 │ 6 │ Negative kills max, keep -12 min
3 │ 4 │ 4 │ -48 │ 6 │ Start fresh with 4
Maximum = 6 from [2, 3] ✓
📊 Complexity Analysis
Time Complexity: O(n)
Single pass through array
Constant work at each position
Total: O(n) ✓
MUCH better than O(n²)! 🚀
Space Complexity: O(1)
Only using a few variables:
- maxSoFar
- minSoFar
- result
- temp variables
No extra arrays needed!
Constant space! ✓
🟢 Approach 3: Optimized DP (Cleaner Code)
💡 Intuition
Same idea as Approach 2, but cleaner implementation:
INSIGHT:
Instead of using temp variables,
we can swap max and min when multiplying by negative!
When current number is negative:
maxSoFar × negative = becomes small (could be new min)
minSoFar × negative = becomes large (could be new max)
So SWAP them before multiplying!
This makes the code cleaner and more intuitive!
📝 Implementation
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) return 0;
int maxSoFar = nums[0];
int minSoFar = nums[0];
int result = nums[0];
for (int i = 1; i < nums.length; i++) {
// If current number is negative, swap max and min
// because multiplying by negative flips them!
if (nums[i] < 0) {
int temp = maxSoFar;
maxSoFar = minSoFar;
minSoFar = temp;
}
// Update max and min
maxSoFar = Math.max(nums[i], maxSoFar * nums[i]);
minSoFar = Math.min(nums[i], minSoFar * nums[i]);
// Update result
result = Math.max(result, maxSoFar);
}
return result;
}
}
Why the Swap Works:
Before multiplying by NEGATIVE number:
maxSoFar = 6 (positive, large)
minSoFar = 3 (positive, small)
After swap:
maxSoFar = 3 (now we'll multiply this by negative)
minSoFar = 6 (now we'll multiply this by negative)
Multiply by -2:
maxSoFar = max(-2, 3 × -2) = max(-2, -6) = -2
minSoFar = min(-2, 6 × -2) = min(-2, -12) = -12 ✓
The swap ensures:
- Small positive × negative = less negative (could be new max)
- Large positive × negative = very negative (could be new min)
Clever trick! 🎯
📊 Complexity Analysis
Time Complexity: O(n) Space Complexity: O(1)
Same as Approach 2, just cleaner code!
🔵 Approach 4: Two-Pass Solution (Left-Right Scan)
💡 Intuition
A completely different perspective: Scan from both directions!
KEY INSIGHT:
The maximum product subarray either:
1. Doesn't contain any zeros
→ Full product from left or right scan works
2. Contains zeros
→ Zeros break the array into segments
→ Maximum is in one of the segments
STRATEGY:
Scan from LEFT: multiply as we go, track max
Scan from RIGHT: multiply as we go, track max
When we hit zero: reset product to 1
The answer is the maximum from both scans!
WHY THIS WORKS:
If there are even number of negatives: left scan finds it
If there are odd number of negatives: right scan finds it
(One scan will avoid the problematic negative!)
Example to Show Why Two Scans:
Array: [2, -3, -4, 5]
Left scan:
2 → product = 2, max = 2
-3 → product = -6, max = 2
-4 → product = 24, max = 24 ✓ (even negatives!)
5 → product = 120, max = 120 ✓
Right scan:
5 → product = 5, max = 5
-4 → product = -20, max = 5
-3 → product = 60, max = 60
2 → product = 120, max = 120 ✓
Both find 120! Both scans ensure we don't miss the answer!
Now try: [2, -3, 4]
Left scan:
2 → product = 2, max = 2
-3 → product = -6, max = 2
4 → product = -24, max = 2 (one negative ruins it)
Right scan:
4 → product = 4, max = 4 ✓
-3 → product = -12, max = 4
2 → product = -24, max = 4
Right scan finds 4! This is why we need both directions!
📝 Implementation
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int maxProduct = nums[0];
// Left to right scan
int product = 1;
for (int i = 0; i < n; i++) {
product *= nums[i];
maxProduct = Math.max(maxProduct, product);
// Reset if we hit zero
if (product == 0) {
product = 1;
}
}
// Right to left scan
product = 1;
for (int i = n - 1; i >= 0; i--) {
product *= nums[i];
maxProduct = Math.max(maxProduct, product);
// Reset if we hit zero
if (product == 0) {
product = 1;
}
}
return maxProduct;
}
}
📊 Complexity Analysis
Time Complexity: O(n)
Two passes through array: 2n = O(n)
Space Complexity: O(1)
Only a few variables
🎯 Pattern Recognition - Product Problems
Core Pattern: Track Both Extremes
When dealing with PRODUCTS (not sums):
→ Negative numbers can flip values
→ Must track BOTH maximum AND minimum
Template:
maxSoFar = tracks best product ending here
minSoFar = tracks worst product ending here
At each position:
maxSoFar = max(current, max×current, min×current)
minSoFar = min(current, max×current, min×current)
Similar Problems:
- Maximum Product of Three Numbers
- Product Except Self
- Sign of Product of Array
⚠️ Important Edge Cases to Test
nums = [2, 3, -2, 4] // Expected: 6
nums = [-2, 0, -1] // Expected: 0
nums = [-2] // Expected: -2
nums = [0, 2] // Expected: 2
nums = [-2, 3, -4] // Expected: 24 (all three)
nums = [2, -5, -2, -4, 3] // Expected: 24
nums = [0, -2, 0] // Expected: 0
nums = [-1, -2, -3, -4] // Expected: 24 (even negatives)
nums = [-1, -2, -3] // Expected: 6 (skip first negative)
nums = [2, -1, 3, -1, 4] // Expected: 4
📝 Quick Revision Notes
🎯 Core Concept
Problem: Find continuous subarray with maximum product.
Key Insight: Track BOTH max and min products because negative × negative = positive!
Why Different from Max Sum: Negatives can flip! A large negative can become a large positive later.
Four Approaches: 1. Brute Force → Try all subarrays, O(n²) ❌ 2. DP Max/Min → Track both extremes, O(n), O(1) ⭐ 3. DP with Swap → Cleaner code, O(n), O(1) ⭐ 4. Two-Pass → Left/right scan, O(n), O(1) ✓
⚡ Quick Implementation
public class Solution {
public int maxProduct(int[] a) {
// // Approach 1 - brute force
// return recursive(a);
// Approach 2 - DP
return dp(a);
}
private int dp(int[] a) {
// At every point, we need to find max and min.
// Find max and min for the subarray ending at i.
int max = a[0];
int min = a[0];
int res = a[0];
// For [2,3,-2,4]
// max: [2,6,-2,4] and min: [2,3,-12,-48]
for (int i = 1; i < a.length; i++) {
int currMax = Math.max(a[i], Math.max(max * a[i], min * a[i]));
int currMin = Math.min(a[i], Math.min(max * a[i], min * a[i]));
// Why like this?
// if we do not do like this, max in above statement
// will be used in the next statement which will go wrong.
max = currMax;
min = currMin;
res = Math.max(res, Math.max(max, min));
}
return res;
}
private int recursive(int[] a) {
int len = a.length;
int res = Integer.MIN_VALUE;
for (int start = 0; start < len; start++) {
int running = a[start];
int currMax = a[start];
for (int end = start - 1; end >= 0; end--) {
running = running * a[end];
currMax = Math.max(currMax, running);
}
res = Math.max(res, currMax);
}
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.maxProduct(new int[] { 2, 3, -2, 4 }) == 6);
System.out.println(s.maxProduct(new int[] { -2, 0, -1 }) == 0);
System.out.println(s.maxProduct(new int[] { -4, -3, -2 }) == 12);
}
}
🔑 Key Insights
Why Track Minimum:
minSoFar might be very NEGATIVE
But negative × negative = POSITIVE!
The "worst" can become the "best"!
Example: [-2, -3]
After -2: min = -2
After -3: -2 × -3 = 6 ✓ (min became max!)
Three Choices at Each Step:
1. Start fresh: nums[i]
2. Extend max: maxSoFar × nums[i]
3. Extend min: minSoFar × nums[i]
Take best for max, worst for min!
Zero Resets Everything:
Product including zero = 0
Zero breaks the chain
Must restart after each zero
🎪 Memory Aid
"Track BOTH max and min - negatives flip!"
"Three choices: fresh, extend max, extend min!"
"Zero resets the product chain!"
"Minimum today = maximum tomorrow!" ✨
⚠️ Common Mistakes
- ❌ Only tracking maximum (forgetting minimum)
- ❌ Not considering "start fresh" option
- ❌ Forgetting negative × negative = positive
- ❌ Not handling zeros correctly
- ❌ Using result variable without initializing
✅ Interview Talking Points
"This is different from Maximum Sum Subarray because
of how negative numbers work with multiplication.
Key insight:
- Negative × Negative = Positive
- Must track BOTH maximum AND minimum products
- The minimum might flip to become maximum!
Approach:
At each position, we have 3 choices:
1. Start fresh from current element
2. Extend the maximum product
3. Extend the minimum product
Take the best for max, worst for min
Track global maximum throughout
Why we need minimum:
Example: [2, -3, -4]
After -3: min = -6 (very negative)
After -4: -6 × -4 = 24 (min became max!)
Complexity: O(n) time, O(1) space
This is optimal!"
🎉 Congratulations!
You've mastered Maximum Product Subarray!
What You Learned:
✅ Products vs Sums - Why products need different approach
✅ Track Both Extremes - Maximum AND minimum needed
✅ Negative Flip - Understanding negative × negative
✅ Three Choices - Fresh start, extend max, extend min
✅ Zero Handling - Zeros break the product chain
✅ O(n) Solution - Single pass, constant space
You've mastered a tricky DP variant! 🚀✨