Problem Statement

Maximum Product Subarray

You are given a list of whole numbers called nums. A subarray is just a chunk of the list that sits next to each other, with no gaps. Your job is to pick the chunk whose numbers, all multiplied together, give the biggest possible result, and return that result. The test cases are set up so the answer always fits in a 32-bit integer, which is a normal-sized number a computer handles easily, so you do not need to worry about it getting too large.

mediumDynamic ProgrammingDynamic ProgrammingTime: O(n) · Space: O(1)

Signals to notice

maximum product of contiguous subarraynegative numbers flip signboth min and max matter

Brute force first

Check every subarray's product. Computes each product from scratch without reusing previous results. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Track both current max and current min at each position. A negative number flips them — the most negative becomes the most positive when multiplied by a negative. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `nums=[2,3,-2,4]`

init: max_prod=2, min_prod=2, result=2 (all = nums[0])
num=3: cands=(3, 2*3=6, 2*3=6) -> max_prod=6, min_prod=3, result=max(2,6)=6
num=-2: cands=(-2, 6*-2=-12, 3*-2=-6) -> max_prod=-2, min_prod=-12, result=max(6,-2)=6
num=4: cands=(4, -2*4=-8, -12*4=-48) -> max_prod=4, min_prod=-48, result=max(6,4)=6
loop ends -> return result = 6

What must stay true

At each element, the maximum product ending here is max(nums[i], maxSoFar * nums[i], minSoFar * nums[i]). You need both extremes because a negative can flip the minimum into the maximum. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

maxP = minP = result = nums[0]
for num in nums[1:]:
    cands = (num, maxP*num, minP*num)
    maxP, minP = max(cands), min(cands)   # swap-aware: neg flips extremes
    result = max(result, maxP)
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Only tracking the maximum — negative × negative = positive, so the minimum product can suddenly become the maximum. You MUST track both. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Dynamic Programming Pattern