LeetCode #152 Hard

Maximum Product Subarray

Contiguous subarray with the largest product. Negatives and zeros lurk in the array.

dparraykadane

02

Intuition

💡

Kadane's trick almost works, but a negative number flips the world: the smallest (most negative) product so far becomes the biggest after multiplying by a negative. So track two running values — the max AND the min product ending here. Each new element either starts fresh or extends one of them; a zero resets both.

03

Approach

1

Why plain Kadane breaks

With sums, a bigger prefix is always better. With products, [-2, 3, -4]: the best answer 24 routes through the most negative prefix −6. Discarding minima loses the answer.

2

Track a (max, min) pair

For each x: candidates are {x, x·curMax, x·curMin}. New curMax = max of them, new curMin = min of them. A negative x swaps the roles — which is exactly why both are kept.

3

Answer is the best curMax seen

Update the global answer each step. Zeros make both candidates collapse toward x=0, restarting the window naturally.

04

Solution & live demo

python

▶1class Solution:
▶2    def maxProduct(self, nums):
▶3        ans = cur_max = cur_min = nums[0]
▶4        for x in nums[1:]:
▶5            cands = (x, x * cur_max, x * cur_min)
▶6            cur_max, cur_min = max(cands), min(cands)
▶7            ans = max(ans, cur_max)
▶8        return ans

05

Edge cases

Single negative element

Answer is that element — 'start fresh at x' candidate covers it.

Zeros in the array

Both trackers pass through 0 and restart after it.

Even vs odd count of negatives

The min-tracker carries the odd-negative prefix until a second negative flips it positive.

06

Complexity

Time

O(n)

Space

O(1)

One pass, two running products.