Maximum Product Subarray — Tracking Min and Max

Maximum Product Subarray looks like a small twist on Kadane’s algorithm for maximum sum, but the twist matters. A single negative number can flip a large product into a large negative, and two negatives can multiply back into a huge positive. The fix is to track both the running min and the running max.

The Problem

Given an integer array nums, find a contiguous subarray (containing at least one number) which has the largest product, and return its product.

Examples:

• nums = [2, 3, -2, 4] returns 6 from [2, 3].
• nums = [-2, 0, -1] returns 0 from [0].
• nums = [-2, 3, -4] returns 24 from the whole array.

The last example is the one to internalize. Even though -2 * 3 = -6 is the minimum so far, multiplying by another -4 turns it into the maximum 24.

Intuition

Kadane works for maximum sum because adding a positive always increases the running sum and adding a negative always decreases it. Products break that monotonicity: multiplying by a negative swaps “best” and “worst”.

So at every index we need to know two things: the largest product of any subarray ending here and the smallest product of any subarray ending here. The smallest, if very negative, may become the largest after the next negative multiplication.

Maintain three values as you sweep left to right: cur_max, cur_min, and result. At each step, the new cur_max is the largest of (num, cur_max * num, cur_min * num). Similarly for cur_min. The trick newcomers miss is computing the candidates before reassigning cur_max. If you update cur_max first, cur_min will use the new value and produce wrong answers.

Explanation with Example

Walk through [-2, 3, -4]. Initial: cur_max = -2, cur_min = -2, result = -2.

• num = 3. Candidates (3, -6, -6). cur_max = 3, cur_min = -6, result = 3.
• num = -4. Candidates (-4, -12, 24). cur_max = 24, cur_min = -12, result = 24.

Return 24. The carefully kept cur_min = -6 was what allowed the final multiplication by -4 to produce 24.

num:        -2     3     -4
cur_max:    -2     3     24
cur_min:    -2    -6    -12
result:     -2     3     24

step 3: candidates = (-4, 3*-4=-12, -6*-4=24)
      cur_min (-6) flipped sign and won max

Zero is a natural reset. When num = 0, all three candidates are 0, and the next iteration treats the next number as a fresh start.

Code

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        cur_max = cur_min = result = nums[0]
        for num in nums[1:]:
            candidates = (num, cur_max * num, cur_min * num)
            cur_max = max(candidates)
            cur_min = min(candidates)
            result = max(result, cur_max)
        return result

class Solution {
    public int maxProduct(int[] nums) {
        int curMax = nums[0], curMin = nums[0], result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];
            int a = curMax * n, b = curMin * n;
            curMax = Math.max(n, Math.max(a, b));
            curMin = Math.min(n, Math.min(a, b));
            result = Math.max(result, curMax);
        }
        return result;
    }
}

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int curMax = nums[0], curMin = nums[0], result = nums[0];
        for (size_t i = 1; i < nums.size(); ++i) {
            int n = nums[i];
            int a = curMax * n, b = curMin * n;
            curMax = max(n, max(a, b));
            curMin = min(n, min(a, b));
            result = max(result, curMax);
        }
        return result;
    }
};

Two local snapshots before overwriting curMax are essential in any language.

Edge Cases

A few inputs are worth testing manually:

• Single element. The loop never runs; result is correctly nums[0].
• All negatives, even count. The whole array is the answer.
• All negatives, odd count. Drop one endpoint to get an even count of negatives.
• Contains zero. The algorithm resets through the zero correctly.

You do not need to hand-code any of these branches. The min-max tracking handles them all.

Complexity Analysis

Time complexity is O(n). One pass with constant-time work per element. Space complexity is O(1) — a fixed set of integer variables.

A Brute-Force Baseline

For interview purposes, mention the O(n^2) brute force first: try every starting index and extend rightward, multiplying as you go. This baseline lets you motivate the linear solution as “we noticed we are recomputing products, and we can track the necessary state in two variables.”

Wrapping Up

Maximum Product Subarray is a great example where the right algorithm is short but only obvious once you have seen the trick. The min-max tracking pattern shows up in problems involving signed values and negation-flavored DP. Internalize the candidate tuple (num, cur_max * num, cur_min * num) and the rest is muscle memory.