Maximum Product Subarray

Difficulty: Medium
Topics: Array, Dynamic Programming
Link: https://leetcode.com/problems/maximum-product-subarray/

Problem Description

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 * 104
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Solution

1. Problem Deconstruction

Technical Definition
Given an array nums of integers, identify the contiguous subarray with maximum multiplicative product. Return this product value.

Beginner Explanation
Find a consecutive group of numbers in the list that, when multiplied together, give the biggest possible result.

Mathematical Formulation
Let array be $nums[0..n-1]$ . Find:

\max_{\substack{0 \leq i \leq j < n}} \left( \prod_{k=i}^{j} nums[k] \right)

Constraint Analysis

Array Length (1 <= n <= 2e4):
- Eliminates O(n²) brute-force approaches.
- Requires O(n) or O(n log n) algorithms.
Element Range (-10 <= nums[i] <= 10):
- Products alternate signs with negative counts.
- Zeros act as subarray resets.
32-bit Product Guarantee:
- No need for big integer handling.
- Focus purely on logical correctness.

Hidden Edge Cases

Single-element arrays (return element itself).
All-negative arrays (even count → product positive).
Alternating zeros and negatives (e.g., [0,-5,0,-3]).

2. Intuition Scaffolding

Real-World Metaphor
Imagine a stock portfolio where daily returns are multiplicative (e.g., +10% = ×1.1, -5% = ×0.95). To find the best-performing consecutive days, negatives can flip losses into gains if followed by another drop.

Gaming Analogy
In a dungeon crawler, each room gives a power multiplier. Some rooms (negatives) weaken you, but two in a row might boost you. Track both current strength and potential from prior weaknesses.

Math Analogy
Maintain running max/min products since:

\text{max}_i = \max(\text{num}_i, \text{max}_{i-1} \times \text{num}_i, \text{min}_{i-1} \times \text{num}_i)

Common Pitfalls

Ignoring Minimums: Negative × negative = positive.
Zero Reset Mishandling: Failing to restart product tracking after zeros.
Greedy Miscalculations: Assuming local maxima imply global maxima.
Single Element Edge Case: Overlooking arrays like [-5].
Overflow Assumptions: Not trusting problem’s 32-bit guarantee.

3. Approach Encyclopedia

Brute Force (Rejected)

Check all possible subarrays, compute products.
Time Complexity: O(n²) → 2e8 operations (impossible for n=2e4).

Optimal Dynamic Tracking

Track current_max and current_min at each step.
Update global maximum after each iteration.

Pseudocode

def maxProduct(nums):  
    if not nums:  
        return 0  
    global_max = current_max = current_min = nums[0]  
    for num in nums[1:]:  
        candidates = (num, current_max * num, current_min * num)  
        current_max = max(candidates)  
        current_min = min(candidates)  
        global_max = max(global_max, current_max)  
    return global_max

Complexity Proof

Time: O(n) → Single pass through array.
Space: O(1) → Fixed variables for tracking.

Visualization

Index: 0   1    2     3  
nums:  2   3   -2     4  
cmax: 2 →6 →-2 →4  
cmin: 2 →3 →-12→-48  
gmax: 2 →6 →6 →6

4. Code Deep Dive

Line-by-Line

def maxProduct(nums):  
    if not nums:  # Handle empty input (constraints say n≥1, but defensive)  
        return 0  
    # Initialize trackers with first element  
    max_product = current_max = current_min = nums[0]  
    for num in nums[1:]:  # Iterate from second element  
        # Compute possible continuations (extend subarray or start fresh)  
        candidates = (num, current_max * num, current_min * num)  
        current_max = max(candidates)  # New local max  
        current_min = min(candidates)  # New local min  
        # Update global best  
        max_product = max(max_product, current_max)  
    return max_product

Edge Case Handling

Example 2 ([-2,0,-1]):
- After -2, process 0 → current_max=0.
- Next -1: current_max becomes max(-1, 0*-1=0, 0*-1=0) = 0.
- Global max remains 0.

5. Complexity War Room

Hardware-Aware Analysis

For n=2e4: 20,000 iterations → ~0.2ms (modern CPU).
Memory: 5 variables → ~20 bytes (negligible).

Industry Comparison

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n²)	O(1)	8/10	❌
Optimal Track	O(n)	O(1)	7/10	✅

6. Pro Mode Extras

Variants

Maximum Product Subsequence (Non-Contiguous):
- Product of all positives + even count of negatives.
Maximum Product with K Elements:
- Dynamic programming with k states.

Interview Cheat Sheet

First Mention: “This requires O(n) time and O(1) space by tracking running max/min.”
Key Insight: “Negatives flip min/max; zeros reset the chain.”
Test Cases: All negatives, single element, zeros at start/end.

#152 - Maximum Product Subarray