Leetcode 152. Maximum Product Subarray

Let's understand what we're being asked to do. We have an array like [2, 3, -2, 4] and need to find the contiguous subarray with the largest product.

Tracing through: [2] has product 2, [2,3] has product 6, [2,3,-2] has product -12, [2,3,-2,4] has product -48. But wait - what about [3,-2,4]? That's -24. And [-2,4]? That's -8. Actually, the subarray [2,3] gives us the maximum product of 6.

Critical insight: Unlike sum problems, negative numbers can flip signs! A negative number multiplied by another negative becomes positive. So we can't just track one running product - we need to track BOTH the maximum AND minimum products at each position.

Why track minimum? Consider [2, -5, -3]. At index 1, the minimum product is -10. When we see -3 at index 2, that minimum -10 becomes 30 (a maximum!). The negative minimum can become a positive maximum when multiplied by another negative.

Edge cases to consider: What if the array contains zeros? (zeros reset the product). What if all numbers are negative? What if there's only one element?

The brute force approach checks every possible contiguous subarray by using nested loops. For each starting position, we iterate through all possible ending positions, calculating the product of elements in that range. We keep track of the maximum product seen across all subarrays. This approach is straightforward but inefficient because it recalculates products from scratch for overlapping subarrays.

def max_product_subarray(nums):
    """
    Find the contiguous subarray with the largest product.
    Uses brute force approach checking all possible subarrays.
    """
    if not nums:
        return 0
    
    max_product = nums[0]
    n = len(nums)
    
    # Try every possible starting position
    for i in range(n):
        current_product = 1
        
        # Try every possible ending position from current start
        for j in range(i, n):
            # Multiply current element into the product
            current_product *= nums[j]
            
            # Update maximum if current product is larger
            max_product = max(max_product, current_product)
    
    return max_product

At each position, we need to track TWO values: the maximum product ending here AND the minimum product ending here.

Why? Because a negative number can flip signs. A large negative product (minimum) becomes a large positive product when multiplied by another negative number. Similarly, a large positive product (maximum) becomes a large negative when multiplied by a negative.

This is fundamentally different from maximum subarray sum problems. With sums, we only track the maximum because adding a negative just makes it smaller.

But with products, negatives can become positives through multiplication. The minimum product at one step might become the maximum product at the next step if we encounter another negative number. We must track both extremes!

Think about walking through [2, -5, -3] step by step:

• At 2: max=2, min=2
• At -5: max=-5 (starting fresh), min=-10 (continuing from 2)
• At -3: max=30 (the min -10 flipped positive!), min=15 (the max -5 became less negative)

The key is that at each number, we consider THREE choices: start fresh with just this number, extend the maximum product, or extend the minimum product. We keep both extremes because either could become the answer later.

The optimal approach uses dynamic programming to track both the maximum and minimum products ending at each position. At each element, we calculate three candidates: the element itself (starting fresh), the element multiplied by the previous maximum (extending positive), and the element multiplied by the previous minimum (which could flip to positive if both are negative). We update both max and min products, then track the global maximum. This handles sign flips elegantly in a single pass.

def max_product_subarray(nums):
    """
    Find the contiguous subarray with the largest product.
    Track both max and min products to handle negative numbers.
    """
    if not nums:
        return 0
    
    # Initialize with first element
    global_max = nums[0]
    current_max = nums[0]
    current_min = nums[0]
    
    # Iterate through remaining elements
    for i in range(1, len(nums)):
        num = nums[i]
        
        # Calculate three candidates
        temp_max = current_max
        candidate1 = num
        candidate2 = num * temp_max
        candidate3 = num * current_min
        
        # Update current max and min
        current_max = max(candidate1, candidate2, candidate3)
        current_min = min(candidate1, candidate2, candidate3)
        
        # Update global maximum
        global_max = max(global_max, current_max)
    
    return global_max

• Dual-state dynamic programming: When dealing with sign-changing operations (multiplication with negatives), track both maximum and minimum products simultaneously - today's minimum can become tomorrow's maximum when multiplied by a negative number, making this dual-tracking essential for correctness.
• State transition with sign awareness: At each position, calculate three candidates: current number alone (starting fresh), max_so_far × current, and min_so_far × current - this handles the case where a large negative number or zero makes it better to restart the subarray rather than continue.
• Space-optimized rolling variables: Use O(1) space by maintaining only `max_ending_here` and `min_ending_here` instead of full DP arrays - since each position only depends on the previous position's values, you can overwrite as you go, making this a constant-space solution.
• Zero-handling edge case: Zeros reset both max and min products to zero, effectively breaking the subarray - ensure your logic naturally handles this by including the current number itself as a candidate (max/min of current alone), which allows the algorithm to restart after encountering zeros.
• Modified Kadane's algorithm pattern: This extends Kadane's maximum subarray technique to multiplicative problems - whenever you have operations that can flip optimality (negatives in multiplication, division, XOR), consider tracking both extremes (max/min) rather than just the maximum.
• Financial portfolio optimization: This pattern applies to compound growth scenarios where negative returns can flip - tracking best and worst case scenarios simultaneously is crucial in risk analysis, investment strategies, and any domain where multiplicative effects and sign changes interact.