Maximum Product Subarray LeetCode 152

LeetCode 152 — Maximum Product Subarray — gives you an integer array nums. Find the contiguous subarray (at least one element) that has the largest product and return that product.

This is the product analog of Maximum Subarray (Kadane's algorithm for sums). The key difference: negative numbers change everything. Two negatives multiply to a positive, so a very negative running product can become the maximum when multiplied by another negative.

The solution tracks both the maximum and minimum product ending at each position. The minimum product is essential because it might become the maximum after multiplication by a negative number. This dual-tracking is the core insight.

Consider nums = [2, 3, -2, 4]. After [2, 3], curMax = 6. Then -2: curMax * -2 = -12, curMin * -2 = -12. But starting fresh: -2 itself. So curMax = max(-12, -12, -2) = -2 and curMin = min(-12, -12, -2) = -12. Then 4: curMax = max(-2*4, -12*4, 4) = max(-8, -48, 4) = 4.

Now consider [2, 3, -2, -4]. After -2, curMin = -12. Then -4: curMin * -4 = 48! The very negative minimum became the maximum. Without tracking curMin, we would miss this. The global max is 48 from the full subarray.

The general principle: at each position, the maximum product ending here comes from one of three sources — extending curMax (if current num is positive), extending curMin (if current num is negative and curMin is negative), or starting fresh with just the current number.

Initialize curMax = curMin = result = nums[0]. For each nums[i] starting from index 1: compute candidates: a = curMax * nums[i], b = curMin * nums[i], c = nums[i]. Update: curMax = max(a, b, c), curMin = min(a, b, c). Update result = max(result, curMax).

Important: use temporary variables for the old curMax when computing curMin, because curMax changes during the update. Either save curMax before updating, or compute both max and min from the same (old) values simultaneously.

The result at the end is the maximum product of any contiguous subarray. Zeros are handled naturally: when nums[i] = 0, all three candidates are 0, so curMax = curMin = 0. The next element starts fresh.

Consider nums = [2, 3, -2, 4]. Init: curMax=2, curMin=2, result=2. i=1 (val=3): candidates: 2*3=6, 2*3=6, 3. curMax=6, curMin=3. result=6.

i=2 (val=-2): candidates: 6*-2=-12, 3*-2=-6, -2. curMax=max(-12,-6,-2)=-2. curMin=min(-12,-6,-2)=-12. result stays 6. i=3 (val=4): candidates: -2*4=-8, -12*4=-48, 4. curMax=max(-8,-48,4)=4. curMin=min(-8,-48,4)=-48. result stays 6.

Answer: 6 (subarray [2, 3]). Now if the array were [2, 3, -2, -4]: at i=3, candidates: -2*-4=8, -12*-4=48, -4. curMax=48. result=48. The full subarray product is 2*3*-2*-4=48.

In Python: curMax = curMin = result = nums[0]. For num in nums[1:]: candidates = (curMax * num, curMin * num, num). curMax, curMin = max(candidates), min(candidates). result = max(result, curMax). Return result.

In Java: use Math.max and Math.min with three arguments via chaining. Save tempMax = curMax before updating: curMax = Math.max(num, Math.max(tempMax * num, curMin * num)). curMin = Math.min(num, Math.min(tempMax * num, curMin * num)). result = Math.max(result, curMax).

The swap variant: if nums[i] < 0, swap curMax and curMin. Then curMax = max(nums[i], curMax * nums[i]) and curMin = min(nums[i], curMin * nums[i]). This is equivalent but avoids computing all three candidates explicitly.

Time complexity is O(n) — a single pass through the array with O(1) work per element. Three multiplications, two comparisons, and one result update per step.

Space complexity is O(1) — only three variables (curMax, curMin, result) regardless of input size. No auxiliary arrays or data structures needed.

This is optimal — we must read every element at least once (any element could be the maximum product by itself or as part of a subarray). The O(1) space is the minimum possible.

Maximum Subarray (LeetCode 53) is the sum version solved by Kadane's algorithm. It only tracks curMax because sums do not flip signs. Understanding both problems reveals when single vs dual tracking is needed.

Product of Array Except Self (LeetCode 238) computes prefix and suffix products — a related product manipulation problem. While not a subarray problem, the prefix product technique builds intuition for how products behave across arrays.

Maximum Length of Subarray with Positive Product (LeetCode 1567) asks for the longest subarray with positive product rather than the largest product value. It uses similar sign-tracking logic but optimizes for length instead of product magnitude.