Problem Description

• LeetCode 152 Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within the array that has the largest product and return that product. This is a variation of the classic maximum subarray problem, but with multiplication instead of addition. The key challenge is handling negative numbers, which can turn a minimum product into a maximum product when multiplied by another negative number, and zeros which reset the product calculations.

Core Algorithm Walkthrough

Both solutions use dynamic programming to track the maximum and minimum products ending at each position. The core insight is that we need to maintain both values because:

• A negative number can flip the maximum to minimum and vice versa
• Two negative numbers multiplied together become positive
• We need to preserve both possibilities as we traverse the array

Solution 1: Direct Calculation Approach This approach directly calculates all possible products at each step:

• max * nums[i]: Extending the current maximum product
• min * nums[i]: Extending the current minimum product
• nums[i]: Starting a new subarray from current element

We then take the maximum of these three for the new max and minimum for the new min.

Solution 2: Swap-Based Approach This approach uses a clever optimization: when encountering a negative number, it swaps the current max and min values before processing. This is because:

• If nums[i] < 0, then max * nums[i] becomes negative (potentially new minimum)
• If nums[i] < 0, then min * nums[i] becomes positive (potentially new maximum)

After swapping, we only need to consider two cases instead of three.

Complexity Analysis

Time Complexity: O(n)

• Single pass through the array for both solutions
• Constant time operations at each step

Space Complexity: O(1)

• Only using a few variables regardless of input size
• No additional data structures needed

Full Solution (Java)

Solution 1: Direct Calculation

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], ans = nums[0];

        // 3 cases:
        // 1. nums[i] itself become max
        // 2. nums[i] is negative, curMin * nums[i] become max
        // 3. nums[i] is positive, curMax * nums[i] become max
        for (int i = 1; i < nums.length; i++) {
            int temp = max; // store max because when updating min max will be updated if you don't store it
            max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);

            if (max > ans) {
                ans = max;
            }
        }
        return ans;
    }
}

Solution 2: Swap-Based Approach

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], ans = nums[0];

        // 3 cases:
        // 1. nums[i] itself become max
        // 2. nums[i] is negative, curMin * nums[i] become max
        // 3. nums[i] is positive, curMax * nums[i] become max
        for (int i = 1; i < nums.length; i++) {

            // swap min and max when encountering negative number
            if (nums[i] < 0) {
                int temp = max;
                max = min;
                min = temp;
            }

            max = Math.max(max * nums[i], nums[i]);
            min = Math.min(min * nums[i], nums[i]);

            ans = Math.max(ans, max);
        }
        return ans;
    }
}

Key Differences:

• Solution 1 is more explicit and considers all three possibilities at each step
• Solution 2 is more optimized, using the swap trick to reduce the number of comparisons
• Both have the same time and space complexity
• Solution 2 is slightly more efficient in practice due to fewer Math.max/Math.min calls

Example trace for nums = [2, 3, -2, 4]:

Solution 1:

• i=1: max=6, min=2, ans=6
• i=2: max=max(6-2, 2-2, -2)=-2, min=min(6-2, 2-2, -2)=-12, ans=6
• i=3: max=max(-24, -124, 4)=4, min=min(-24, -124, 4)=-48, ans=6

Solution 2:

• i=1: max=6, min=2, ans=6
• i=2: nums[i]=-2 (negative), swap → max=2, min=6, then max=-2, min=-12, ans=6
• i=3: max=4, min=-48, ans=6

Both solutions correctly handle the alternating signs and find the maximum product subarray efficiently.