Find maximum product subarray

Problem Statement

Given an integer array, find the contiguous subarray with the maximum product.

Example:

• Input: [2, 3, -2, 4]
• Output: 6
• Explanation: Subarray [2, 3] has the maximum product = 6

Approach 1: Brute Force

Intuition

Check all possible subarrays and calculate their products. Track the maximum product found.

Algorithm

1. For each starting index i
2. For each ending index j >= i
3. Calculate product of subarray [i, j]
4. Track maximum product

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

Complexity Analysis

• Time Complexity: O(n²) - Optimized brute force with running product
• Space Complexity: O(1) - No extra space used

Approach 2: Dynamic Programming (Optimal)

Intuition

Unlike maximum sum subarray, product can become larger when multiplying a negative number with another negative number. So we track both maximum and minimum products ending at each position.

Algorithm

1. Track maxSoFar and minSoFar at each position
2. For each element:
   • New max can be: current element, maxSoFar × current, or minSoFar × current
   • New min can be: current element, maxSoFar × current, or minSoFar × current
3. Update global maximum

public 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++) {
            int curr = nums[i];
            
            // Temp variable needed because maxSoFar changes before we use it
            int tempMax = Math.max(curr, Math.max(maxSoFar * curr, minSoFar * curr));
            minSoFar = Math.min(curr, Math.min(maxSoFar * curr, minSoFar * curr));
            maxSoFar = tempMax;
            
            result = Math.max(result, maxSoFar);
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass
• Space Complexity: O(1) - Only constant extra space

Approach 3: Two-Pass Prefix/Suffix Product

Intuition

The maximum product subarray either starts from the left, ends at the right, or is bounded by zeros. Compute prefix and suffix products, resetting when encountering zero.

Algorithm

1. Compute products from left to right (prefix)
2. Compute products from right to left (suffix)
3. Maximum of all prefix and suffix products is the answer

public class Solution {
    public int maxProductTwoPass(int[] nums) {
        int n = nums.length;
        int maxProduct = nums[0];
        
        // Left to right pass
        int product = 1;
        for (int i = 0; i < n; i++) {
            product *= nums[i];
            maxProduct = Math.max(maxProduct, product);
            if (product == 0) product = 1;  // Reset at zero
        }
        
        // Right to left pass
        product = 1;
        for (int i = n - 1; i >= 0; i--) {
            product *= nums[i];
            maxProduct = Math.max(maxProduct, product);
            if (product == 0) product = 1;  // Reset at zero
        }
        
        return maxProduct;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Two passes
• Space Complexity: O(1) - Only constant extra space

Visual Example

For array [2, 3, -2, 4]:

DP Approach:

Two-Pass Approach:

Edge Cases

1. Array with zeros: Product resets at zero
2. All negative numbers: Need to track both max and min
3. Single element: Return that element
4. Contains zero only: Return 0

Key Takeaways

1. Track both max and min because negative × negative = positive
2. Unlike sum, product can "flip" from min to max with one negative number
3. Zeros break the subarray - need to handle specially
4. Two-pass approach is intuitive: max product is in either left prefix or right suffix
5. This is the multiplicative analogue of Kadane's algorithm
6. Watch for integer overflow with large numbers