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.

Sitelet https://gitgood.dev/coding/maximum-product-subarray

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.

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.