Max Product Subarray LeetCode 152 Guide

LeetCode 152 Maximum Product Subarray gives you an integer array nums that can contain positive numbers, negative numbers, and zeros. Your goal is to find the contiguous subarray that has the largest product and return that product. Unlike the maximum subarray sum problem, the presence of negative numbers and zeros makes this significantly more complex.

A single negative number can flip a large positive product into a large negative product, and a large negative product can become the new maximum when multiplied by another negative number. Zeros reset the product entirely, acting as hard boundaries between independent subarray segments. These two characteristics make the naive Kadane's sum approach insufficient.

The brute force approach generates all O(n^2) subarrays and computes the product of each — O(n^3) overall, or O(n^2) with a running product. With n up to 20,000, even O(n^2) is too slow. The optimal solution runs in O(n) time and O(1) space by maintaining two running values instead of one.

Kadane's algorithm for maximum subarray sum maintains a single running value curMax = max(nums[i], curMax + nums[i]). At each step, you either extend the previous subarray or start fresh from the current element. This works for sums because a negative number always reduces the sum — there is no way a negative sum contributes positively to a future sum.

For products, this reasoning breaks. Suppose curMax is -100 (a large negative product) and you encounter -2. The product -100 * -2 = 200 is a large positive — the current maximum. If you only tracked curMax and reset it to max(nums[i], curMax * nums[i]), you'd compute max(-2, -100 * -2) = max(-2, 200) = 200 correctly here. But if curMax were +50 and you encounter -3, then -3 * 50 = -150 is a large negative. Later, if you see another -3, you want -150 * -3 = 450. If you'd discarded the -150 as useless, you'd miss the 450.

The fix is to track both curMax (largest product ending here) and curMin (smallest / most negative product ending here). At each new element, both values are candidates for producing a new max or min through multiplication. A negative element swaps what was max into the new min candidate and vice versa — because multiplying a large positive by a negative yields a large negative, and multiplying a large negative by a negative yields a large positive.

The algorithm iterates through nums once, maintaining curMax, curMin, and globalMax. At each step, if nums[i] is negative, swap curMax and curMin. This pre-swap is the key: after swapping, curMax holds the more-negative value and curMin holds the less-negative (or more-positive) value, so the formulas curMax = max(num, curMax * num) and curMin = min(num, curMin * num) apply correctly without conditional branches inside them.

After the optional swap, update curMax = max(num, curMax * num). This choice means: either start a fresh subarray at the current element (take num alone), or extend the previous best subarray (multiply curMax * num). Similarly, curMin = min(num, curMin * num) — either restart or extend the worst product. After both updates, set globalMax = max(globalMax, curMax).

Initialize all three variables to nums[0] before starting the loop at index 1. This handles the edge case of a single-element array and ensures that the global maximum is at least the first element. Using 0 or 1 as the initial value would give incorrect results for all-negative arrays or arrays where the maximum product subarray is a single negative element.

The minimum (most negative) product at each step is not discarded as useless — it is a "potential bomb" that becomes the maximum when multiplied by a negative number later. Without tracking curMin, the algorithm would lose information about large negative products, missing opportunities where two negatives multiply to a large positive.

Consider [-3, -2, -5]. After index 0: curMax = -3, curMin = -3, globalMax = -3. At index 1, num = -2 is negative so swap: curMax = -3, curMin = -3 (same here since equal). curMax = max(-2, -3 * -2) = max(-2, 6) = 6. curMin = min(-2, -3 * -2) = min(-2, 6) = -2. globalMax = 6. At index 2, num = -5 is negative so swap: curMax = -2, curMin = 6. curMax = max(-5, -2 * -5) = max(-5, 10) = 10. globalMax = 10. The answer is 30 if you continue [-3, -2, -5] = 30. Tracking curMin preserved the large negative product needed for subsequent multiplications.

Zeros are naturally handled by the max/min formulas. When num = 0, curMax * 0 = 0 and curMin * 0 = 0, so max(0, 0) = 0 and min(0, 0) = 0. Both curMax and curMin reset to 0, effectively starting fresh. The next element will then be compared against 0*next = 0, and max(next, 0) = next if next > 0, or min(next, 0) = next if next < 0 — both correct.

Trace [2, 3, -2, 4]: Init curMax = curMin = globalMax = 2. Step i=1, num=3: no swap. curMax = max(3, 2*3) = 6. curMin = min(3, 2*3) = 3. globalMax = 6. Step i=2, num=-2: swap → curMax = 3, curMin = 6. curMax = max(-2, 3*-2) = max(-2, -6) = -2. curMin = min(-2, 6*-2) = min(-2, -12) = -12. globalMax = max(6, -2) = 6. Step i=3, num=4: no swap. curMax = max(4, -2*4) = max(4, -8) = 4. curMin = min(4, -12*4) = min(4, -48) = -48. globalMax = max(6, 4) = 6. Answer: 6 (subarray [2,3]).

Trace [-2, 0, -1]: Init curMax = curMin = globalMax = -2. Step i=1, num=0: no swap (0 not negative). curMax = max(0, -2*0) = 0. curMin = min(0, -2*0) = 0. globalMax = max(-2, 0) = 0. Step i=2, num=-1: swap → curMax = 0, curMin = 0. curMax = max(-1, 0*-1) = max(-1, 0) = 0. curMin = min(-1, 0*-1) = min(-1, 0) = -1. globalMax = max(0, 0) = 0. Answer: 0. The zero separates the two negative numbers so they cannot multiply together; the best product is 0.

These two traces illustrate the most important cases: a negative breaking a product chain (first example), and a zero acting as a hard reset boundary (second example). The swap-then-update pattern handles both seamlessly without any special-case branches in the main logic.

Python implementation: def maxProduct(nums): curMax = curMin = globalMax = nums[0]; for num in nums[1:]: if num < 0: curMax, curMin = curMin, curMax; curMax = max(num, curMax * num); curMin = min(num, curMin * num); globalMax = max(globalMax, curMax); return globalMax. This is 7 lines. The swap is a single tuple assignment. Time O(n), space O(1). Compare to maxSubArray which uses curMax = max(num, curMax + num) with no curMin needed — products require the extra tracking that sums do not.

Java implementation: public int maxProduct(int[] nums) { int curMax = nums[0], curMin = nums[0], globalMax = nums[0]; for (int i = 1; i < nums.length; i++) { int num = nums[i]; if (num < 0) { int tmp = curMax; curMax = curMin; curMin = tmp; } curMax = Math.max(num, curMax * num); curMin = Math.min(num, curMin * num); globalMax = Math.max(globalMax, curMax); } return globalMax; } Java requires a temp variable for the swap since tuple assignment is not supported. Otherwise the logic is identical.

An alternative formulation avoids the explicit swap by computing all four products at once: newMax = max(num, curMax*num, curMin*num); newMin = min(num, curMax*num, curMin*num). This eliminates the branch at the cost of two extra multiplications per step. Both formulations are O(n) time O(1) space and produce the same result — choose based on code clarity preference.

Maximum Subarray (LeetCode 53) is the sum analog: Kadane's with a single curMax. Maximum Product Subarray (LeetCode 152) is the product variant requiring curMin. Best Time to Buy and Sell Stock (LeetCode 121) tracks a running minimum price instead of a running maximum product — similarly O(n) with a single auxiliary variable. These three problems form the core "running-value DP" family.

Product of Array Except Self (LeetCode 238) builds prefix and suffix product arrays without division, using the same observation that negative numbers affect product sign globally. Word Break and Coin Change use DP arrays rather than running values but belong to the same dynamic programming paradigm: define a subproblem at each index and build the answer incrementally.

For interview preparation, the progression is: master Maximum Subarray (Kadane's sum), then Maximum Product Subarray (Kadane's product with curMin), then Best Time to Buy and Sell Stock (running min price). Once comfortable with the swap trick and two-variable DP, problems like Maximum Product of Three Numbers and Subarray Product Less Than K become straightforward extensions.