Maximum Product Subarray
Maintained by Vikas D, software engineer
You are given an array of integers. A subarray is a run of one or more values that sit next to each other in the original order, with nothing skipped in between. Your job is to look at every possible run and report the biggest product any of them can produce.
The numbers can be positive, negative, or zero, and that mix is what makes the problem interesting. A negative value can flip a large positive product into a large negative one, but a second negative later on can flip it right back to a large positive. A zero wipes out any running product entirely.
Because the answer can come from a run that starts anywhere, you cannot simply multiply everything together. You need to track how the product evolves as you move across the array and decide, at each step, whether extending the current run or starting fresh gives you more.
Return the single integer that is the maximum product found across all valid subarrays.
Examples
The run [2, 3] multiplies to 6. Extending into -2 would drop the product to -12, and the lone 4 only gives 4, so 6 is the best.
Taking the whole array, (-2) * 3 * (-4) = 24. The two negatives cancel their signs, so the full run beats any shorter piece.
The 0 breaks the array into [-2] and [-1], each negative. No contiguous run beats the single 0, so the answer is 0.
Constraints
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- The product of any prefix or suffix of the array fits in a 32-bit signed integer
- The chosen subarray must contain at least one element
Visible test cases
- maxProduct([2,3,-2,4]) == 6
- maxProduct([-2,0,-1]) == 0
- maxProduct([-2,3,-4]) == 24
- maxProduct([0,2]) == 2
- maxProduct([-3,-1,-1]) == 3
Hints
Hint 1
A negative number does not just shrink a product, it swaps which extreme matters: the smallest (most negative) running product can become the largest after one more negative.
Hint 2
So at each index track two values together, the largest product ending here and the smallest product ending here, instead of only the maximum.
Hint 3
When the current number is negative, swap your running max and min before updating, since multiplying by a negative turns the smallest into the largest and vice versa. Reset by comparing against the number itself to handle zeros and fresh starts.
Approaches
Brute force over all subarrays
Time O(n^2) · Space O(1)Try every start index, extend to every end index, multiply the run as you go, and keep the best product seen.
- Set a running answer to the first element so a single value is always considered.
- For each start index i, set a running product to 1.
- For each end index j from i forward, multiply the running product by nums[j] and compare it to the answer.
- After all pairs are checked, return the answer.
Optimal one-pass max/min tracking
Time O(n) · Space O(1)Carry both the maximum and minimum product ending at the current position. The minimum matters because a future negative can turn the most negative product into the largest.
- Initialize curMax, curMin, and the answer all to nums[0].
- Walk from the second element to the end. For each value n, if n is negative, swap curMax and curMin first, because multiplying by a negative flips which one leads.
- Set curMax to the larger of n and curMax * n, and curMin to the smaller of n and curMin * n. Comparing against n alone restarts the run, which naturally handles zeros.
- Update the answer with curMax, then return the answer after the loop.
Common mistakes
- Tracking only the running maximum and ignoring the running minimum, which fails the moment two negatives should combine into a large positive.
- Forgetting to swap max and min when the current value is negative, so the sign flip is not accounted for.
- Not resetting on zero. Comparing the new product against the bare number n at each step is what lets a zero start a fresh run instead of poisoning every later product.
- Seeding the answer with 0 or 1 instead of nums[0]. An all-negative array like [-3, -1, -1] or a single negative element would then return a wrong value.
- Assuming the answer is the product of the entire array, which breaks as soon as a single negative or zero appears.
Follow-up variations
- Return the actual start and end indices of the best subarray, not just its product.
- Solve the same problem for the maximum sum subarray instead of the product (classic Kadane).
- Handle floating point values where rounding and very small magnitudes change how you compare products.
- Extend to a 2D grid and find the submatrix with the largest product.
- Support a streaming version where numbers arrive one at a time and you must answer after each arrival.