Maximum Product Subarray: LeetCode 152 Track Min and Max

If you have solved Maximum Subarray (#53) with Kadane's Algorithm, you already know how to track a running maximum as you scan left to right. Maximum Product Subarray (#152) looks nearly identical on the surface — find the contiguous subarray with the largest product instead of the largest sum. But one subtle difference changes everything: negative numbers.

With addition, a negative number always hurts your running total. With multiplication, a negative number can flip your smallest (most negative) running product into the largest positive product in a single step. That one insight is the entire key to solving this maximum product subarray leetcode problem, and it is exactly what interviewers want to hear you articulate.

This walkthrough covers why Kadane's alone fails for products, the two-variable tracking technique that fixes it, a step-by-step visual example, and the edge cases that trip up candidates. By the end, you will have a clean O(n) time, O(1) space solution and the intuition to explain it confidently.

Given an integer array nums, find the contiguous subarray (containing at least one number) that has the largest product, and return that product. The array can contain positive numbers, negative numbers, and zeros. This is LeetCode 152, and it appears frequently in interviews at top tech companies.

The brute-force approach checks every possible subarray, computes the product, and tracks the maximum — an O(n^2) solution at best. But just like Maximum Subarray, there is a linear-time approach. The challenge is figuring out what state to carry forward as you iterate.

Kadane's Algorithm works for Maximum Subarray because addition has a straightforward property: if your running sum goes negative, you are better off restarting from the current element. You only ever need to track the running maximum. But multiplication breaks that assumption completely.

Consider the array [-2, 3, -4]. If you only track the running maximum product, you would see -2, then 3 (restart), then -4 (restart again) — giving you a final answer of 3. But the actual maximum product is 24, because (-2) * 3 * (-4) = 24. The most negative running product multiplied by another negative became the largest positive product.

This is the core insight for the leetcode 152 solution: a negative times a negative is positive, so today's minimum could become tomorrow's maximum. You cannot discard the minimum — you must carry it forward alongside the maximum.

The fix is elegant: at each element, maintain both a running maximum product and a running minimum product. At every step, you have three candidates for the new maximum: the current number alone (which restarts the subarray), the current number times the previous maximum, or the current number times the previous minimum. You take the max of all three. You do the same for the minimum, taking the min of all three candidates.

Here is the logic in plain terms. Initialize maxSoFar and minSoFar to the first element. For each subsequent element, compute tempMax = max(num, num * maxSoFar, num * minSoFar) and tempMin = min(num, num * minSoFar, num * maxSoFar). Update maxSoFar = tempMax and minSoFar = tempMin. Track the global maximum across all steps. The final global maximum is your answer.

This kadane product variant runs in O(n) time with O(1) space — identical complexity to the original Kadane's Algorithm. The only difference is maintaining two variables instead of one. It handles positives, negatives, and zeros naturally without any special-case branching.

Let's walk through the array [2, 3, -2, 4] step by step. Start with maxSoFar = 2, minSoFar = 2, globalMax = 2. At element 3: candidates are 3, 3*2=6, 3*2=6. So maxSoFar = 6, minSoFar = 3, globalMax = 6. At element -2: candidates are -2, -2*6=-12, -2*3=-6. So maxSoFar = -2, minSoFar = -12, globalMax stays 6. At element 4: candidates are 4, 4*(-2)=-8, 4*(-12)=-48. So maxSoFar = 4, minSoFar = -48, globalMax stays 6. Answer: 6 (subarray [2, 3]).

Now try [-2, 0, -1]. Start with maxSoFar = -2, minSoFar = -2, globalMax = -2. At element 0: candidates are 0, 0*(-2)=0, 0*(-2)=0. So maxSoFar = 0, minSoFar = 0, globalMax = 0. At element -1: candidates are -1, -1*0=0, -1*0=0. So maxSoFar = 0, minSoFar = -1, globalMax stays 0. Answer: 0.

Notice how the zero in the second example naturally reset both the min and max product. This is not a special case you need to handle — it falls out of the three-candidate comparison automatically. The 'num alone' candidate handles the restart, and since 0 times anything is 0, the products collapse.

The max product subarray problem has several edge cases worth thinking through before your interview. Each one is handled naturally by the track-min-max approach, but understanding why builds confidence.

A single-element array returns that element immediately — the algorithm initializes globalMax to the first element, so this works with no iteration. An array of all negatives (like [-3, -1, -2]) returns the least negative element, because the algorithm correctly tracks the maximum at each step. An array with a single zero in the middle (like [2, -5, 0, 3, -1]) splits into two independent subproblems on either side of the zero.

The maximum product explained in this article boils down to one concept: sometimes you need to track dual running values because the operation (multiplication) does not have the same monotonic property as addition. This exact pattern — maintaining both a best-case and worst-case running value — appears in several other problems.

Binary Tree Maximum Path Sum (#124) is a classic example: you return one value up to your parent but track a different (potentially larger) value as the global answer. Best Time to Buy and Sell Stock problems use a similar idea of tracking a running minimum alongside your answer. Recognizing this dual-tracking pattern saves time in interviews because you can explain the connection immediately.

Practice this problem alongside Maximum Subarray (#53) to solidify the contrast. YeetCode flashcards pair these problems together so you can drill the distinction through spaced repetition — helping you recall the min-max tracking technique when it matters most.