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 fits in a 32-bit integer.

Examples

Constraints

• 1 ≤ nums.length ≤ 2 * 10⁴
• -10 ≤ nums[i] ≤ 10
• The product of any prefix or suffix of nums fits in a 32-bit integer.

Tracking Both Min and Max Products to Handle Negative Signs

In maximum sum subarray problems (like Kadane’s algorithm), we only track the maximum sum. Negative numbers always decrease the sum, so we can discard negative prefix sums.

For products, this logic breaks because of sign flips: multiplying two negative numbers yields a positive number. A very small negative product (like -100) can instantly become the maximum positive product (+200) if it is multiplied by another negative number (like -2).

Therefore, at each step, we must maintain two states:

• The maximum product ending at the current index.
• The minimum product (which could be highly negative) ending at the current index.

When we process the next number nums[i]:

• If nums[i] is negative, the maximum product becomes the minimum product multiplied by nums[i], and vice versa.
• The new states are updated as max_product = max(nums[i], nums[i] * max_prev, nums[i] * min_prev) and min_product = min(nums[i], nums[i] * max_prev, nums[i] * min_prev).

Solution 1: Dynamic Programming (Constant Space)

Iterate through the array, tracking and updating both the minimum and maximum products at each position.

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int globalMax = nums[0];
        int currMax = nums[0];
        int currMin = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];

            // if the current number is negative, min and max products swap
            if (num < 0) {
                int temp = currMax;
                currMax = currMin;
                currMin = temp;
            }

            currMax = Math.max(num, currMax * num);
            currMin = Math.min(num, currMin * num);

            globalMax = Math.max(globalMax, currMax);
        }

        return globalMax;
    }
}

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        if not nums:
            return 0

        global_max = nums[0]
        curr_max = nums[0]
        curr_min = nums[0]

        for i in range(1, len(nums)):
            num = nums[i]

            # if the current number is negative, min and max products swap
            if num < 0:
                curr_max, curr_min = curr_min, curr_max

            curr_max = max(num, curr_max * num)
            curr_min = min(num, curr_min * num)

            global_max = max(global_max, curr_max)

        return global_max

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxProduct(std::vector<int>& nums) {
        if (nums.empty()) return 0;

        int globalMax = nums[0];
        int currMax = nums[0];
        int currMin = nums[0];

        for (size_t i = 1; i < nums.size(); i++) {
            int num = nums[i];

            // if the current number is negative, min and max products swap
            if (num < 0) {
                std::swap(currMax, currMin);
            }

            currMax = std::max(num, currMax * num);
            currMin = std::min(num, currMin * num);

            globalMax = std::max(globalMax, currMax);
        }

        return globalMax;
    }
};

Complexity Analysis:

• Time Complexity: O(n) where n is the length of array nums. We scan the array once.
• Space Complexity: O(1) auxiliary space as we only use three tracking variables.

Where it breaks: Nothing breaks for standard input arrays. If numbers contain float values, the logic holds, but standard float precision limits can affect calculation accuracy on very long subarrays.

Common Mistakes

• Forgetting to swap currMax and currMin when the multiplier is negative. If you omit the swap, the negative multiplication will convert the large positive product to a large negative, and the small negative product to a large positive, corrupting the states.
• Not storing currMax in a temporary variable before updating currMin. If you update currMax first and then calculate currMin = min(num, currMin * currMax), you will be using the new currMax value instead of the previous one.
• Initializing tracking variables to 1 instead of nums[0]. If the array contains only a single negative number [-2], starting at 1 will yield an incorrect result of 1 (or 0) instead of -2.

Frequently Asked Questions

How does this algorithm handle zeros in the input? If nums[i] == 0, both currMax and currMin will be reset to 0. On the next iteration, the algorithm starts fresh (since max(num, 0 * num) = num), which correctly simulates restarting the subarray after a zero boundary.

What is the difference between this and Kadane’s algorithm? Kadane’s algorithm only tracks the maximum prefix sum. This algorithm must track both the maximum and minimum prefix products to accommodate sign flips caused by negative numbers.

What does this problem test in interviews? It tests your capability to identify subproblem dependencies, manage sign changes in dynamic states, and perform swaps to maintain state consistency.

← All Problems