Why track the minimum product as well as the maximum?

Multiplying by a negative number flips signs: the most negative product so far becomes the largest one. Keeping the smallest product means that case is never lost.

Why can't Kadane's algorithm for maximum sum be used directly?

Kadane's keeps one running value because adding a number never reverses the order of two sums. Multiplying by a negative does, so the product version needs both the largest and the smallest running product.

How does a zero affect the answer?

A zero makes both running products zero, and the next number starts fresh because max(x, 0 * x) is x when x is positive. Zero itself is a valid answer when every other subarray product is negative.

Maximum Product Subarray

Find the largest product of a contiguous subarray in one pass by tracking both the largest and the smallest running product.

MediumSolve on LeetCode

Problem Understanding

Maximum Product Subarray: given an integer array nums, return the largest product of any contiguous, non-empty subarray.

Example: nums = [2, 3, -2, 4] returns 6, from the subarray [2, 3]. nums = [-2, 0, -1] returns 0.

Attempt 1: Every Subarray

Fix a start index, extend the end one step at a time and multiply as you go, keeping the largest product. That is O(n²) time. The waste is that every start index recomputes products the previous one already formed.

The Intuition: Two Running Products

For a maximum sum, Kadane's algorithm keeps the best sum ending at the current index. Products need one more value, because a negative number turns the smallest product into the largest.

Keep, for the subarray ending at the current index:

curMax, the largest product, and
curMin, the smallest (most negative) product.

For each new x: if it is negative, swap the two. Then either extend or start fresh at x: curMax = max(x, curMax * x) and curMin = min(x, curMin * x). The answer is the largest curMax seen.

Interactive Walkthrough

The pointer moves one number at a time while curMax, curMin and best update beside the array. On a negative number, watch the swap step: the smallest product is about to become the largest.

Dry Run Table

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

`x`	Swap?	`curMax`	`curMin`	`best`
2 (start)	—	2	2	2
3	no	6	3	6
-2	yes	-2	-12	6
4	no	4	-48	6

The answer is 6, from [2, 3]. At -2 the products 6 and 3 swap places before the multiply, giving curMin = -12; a later negative would turn that into a large positive product.

The Solution Template

One pass with the largest and smallest product ending at each index.

Maximum Product Subarray Code

1var maxProduct = function(nums) {
2    let best = nums[0], curMax = nums[0], curMin = nums[0];
3    for (let i = 1; i < nums.length; i++) {
4        const x = nums[i];
5        if (x < 0) {
6            [curMax, curMin] = [curMin, curMax];
7        }
8        curMax = Math.max(x, curMax * x);
9        curMin = Math.min(x, curMin * x);
10        best = Math.max(best, curMax);
11    }
12    return best;
13};

Edge Cases & Common Mistakes

Single element: the loop never runs; the answer is nums[0], even if it is negative.
Zeros: both products become 0 and the next number starts fresh, so subarrays never span a zero unless the answer is 0 itself.
Only tracking the maximum: [-2, 3, -4] would return 3 instead of 24.
The no-swap version: curMax = max(x, curMax * x, curMin * x) and curMin = min(x, curMax * x, curMin * x) also works, but only if the second line uses the old curMax. Save it before overwriting.

Summary

Maximum Product Subarray is Kadane's algorithm with two running values instead of one: the largest and smallest product ending at each index, swapped whenever a negative number arrives. One pass, O(1) extra space.

More practice: DSA interview questions with answers · patterns cheat sheet

Coin Change II

Combination Sum IV