How do you approach Maximum Product Subarray?

Kadane's algorithm for maximum sum doesn't directly work here - multiplying by a negative number flips large positives into large negatives and vice versa.

What is the time complexity of Maximum Product Subarray?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Maximum Product Subarray?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Maximum Product Subarray

MediumAlgorithms

Description

Given an integer array `nums`, find a contiguous non-empty subarray within the array that has the largest product, and return the product. The test cases are generated so that the product of any subarray of `nums` is guaranteed to fit in a **32-bit** integer.

Example 1

Input: nums = [2,3,-2,4]

Output: 6

Explanation: The subarray [2,3] has the largest product 6.

Example 2

Input: nums = [-2,0,-1]

Output: 0

Explanation: The result cannot be 2 because [-2,-1] is not contiguous.

Example 3

Input: nums = [-2,3,-4]

Output: 24

Explanation: The whole array: (-2) x 3 x (-4) = 24 - two negatives make a positive.

Constraints

- 1 <= nums.length <= 2 * 10^4 - -10 <= nums[i] <= 10 - The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Maximum Product Subarray: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (4 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Kadane's algorithm for maximum sum doesn't directly work here - multiplying by a negative number flips large positives into large negatives and vice versa.
Track BOTH the maximum and the minimum product of a subarray ending at the current index. Why is the minimum worth keeping?
At each element, the new max/min ending here is the best/worst of: the element alone, element * previousMax, element * previousMin. A very negative minimum times a negative element can become the new maximum.

The optimal approach

Show the approach: Kadane Variant with Max and Min Tracks

For each index keep `maxHere` and `minHere`, the largest and smallest products of a subarray ending there. A new element either starts fresh or extends the previous max/min product - and because a negative element swaps the roles, the candidate set is `{x, x * maxPrev, x * minPrev}` for both tracks. The global answer is the best `maxHere` seen.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.