DSA AnimatorDSA animations
Maximum Product Subarray LC #152 Medium DP · Min/Max Track
Problem

Given an integer array nums, find a subarray with the largest product and return the product. Negative × negative = positive, so track both max and min.

Example 1
Input: [2,3,-2,4]
Output: 6
Example 2
Input: [-2,3,-4]
Output: 24
maxP=max(n, maxP*n, minP*n), minP=min(n, maxP*n, minP*n).
Try Examples
Custom:
Approach
Track maxP and minP — negative × negative = positive
maxP = max(n, maxP*n, minP*n), minP = min(n, maxP*n, minP*n). res = max(res, maxP).
Array & Candidates
Load an example to begin.
Variables
i / n
—
maxP
—
minP
—
ans
—
Step Logic
Press ▶ Play or Next Step to begin.
📊
Ready
0 / 0
Select an example and press Play.
Algorithm
1
Track maxP, minP ending at current index
2
minP*n can become max when n is negative
3
maxP = max(n, maxP*n, minP*n)
4
minP = min(n, maxP*n, minP*n), res = max(res, maxP)
Time
O(n)
Space
O(1)
Why This Works

Unlike sum, a negative product can flip to max when multiplied by another negative. Track both max and min product ending here. At each step, new max = n, old max×n, or old min×n.

How to solve Maximum Product Subarray

LeetCode 152 · Medium · Dynamic Programming · Pattern: Track Max and Min

Why the obvious approach is slow

Multiplying every subarray is O(n²). Kadane style tracking of only the maximum fails, because a negative number turns the smallest product into the largest.

The key idea

Track two values for subarrays ending at the current index: the largest product and the smallest product. The smallest one matters because it may be a big negative number. When the current number is negative, swap the two before updating. Then the new maximum is the larger of the number itself and the maximum times the number, and the minimum likewise. Keep the best maximum seen anywhere.

Remember

With products, keep both the maximum and the minimum. A negative number swaps their roles.

Run the animation above on your own input, or watch the 1:54 video explanation of Maximum Product Subarray with a dry run and Java code.

More Dynamic Programming problems