Difficulty: Medium1-D Dynamic Programming

Maximum Product Subarray

Problem in Plain English

Given an integer array, find the largest product of any contiguous non-empty subarray.

Problem Statement

You are given an integer array nums. A subarray takes a contiguous non-empty block.

Return the maximum product over all such blocks. Negatives flip signs, so the best block may hold an even count of them, and zeros split the array into independent parts.

Constraints

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
The product of every subarray fits in a signed 32-bit integer; this includes intermediate products of contiguous blocks.

Examples

Example 1

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

The contiguous block [2, 3] has product 6. Including -2 makes that product negative, and the best block after it is [4] with product 4, so the overall maximum remains 6.

Example 2

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

The one-element block [0] beats both negative singletons. The two negatives cannot multiply to 2 without including the separating zero, which makes the product 0.

Example 3

Input: nums = [-3]
Output: -3

A subarray must be non-empty, so the only candidate is the lone negative value. Initializing the answer to zero would incorrectly allow an empty block.

Example 4

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

The entire block has two negatives and product 24. Before the last value, the minimum ending product is -6; multiplying it by -4 produces the maximum. Keeping only the previous maximum 3 would miss 24.

Intuition

Multiplication can reverse which partial result is useful: in [-2, 3, -4], the smallest product ending at 3 is -6, and the next -4 turns it into the largest product 24. Keep both the maximum and minimum products of non-empty subarrays ending at the current index, rather than only a global maximum. In Example 1, extending [2, 3] by -2 makes -12, so starting again at 4 beats extending that negative block, while the global answer stays 6. Zero makes both ending products zero; the next value can start a new block.

Approaches

Check Every Subarray

Solution Details

Reveal Check Every Subarray: intuition, complexity, and code

Intuition

Fix a start index and extend one running product to each later end. This enumerates all non-empty blocks without recomputing each multiplication chain from scratch; trying all starts still costs quadratic time.

Step-by-Step Logic

Seed best from the first element to require a non-empty result. Example 1 starts with best 2.
For each start, reset a running product to 1, then move the end from that start to the last index, multiplying one newly included element per extension.
Compare each running product with the global best. At start 0 in Example 1, products 2, 6, -12, -48 raise best to 6 and then leave it unchanged.
Repeat for every later start, even after a zero or negative product: a later extension can change signs. Example 1 adds products 3, -6, -24, -2, -8, and 4; none beats 6.
Return the global best after all starts and ends. Example 1 returns 6.

Why It Works

Every non-empty subarray is identified by one start and one end with start no later than end. At the start of each outer iteration the product is 1, and multiplying each next value makes it exactly the product from that start through the current end. The nested loops therefore compute every candidate exactly once. The best is seeded from an actual non-empty subarray and updated with every candidate, so the final value is their maximum even when all candidates are negative.

Dry Run

Check Every Subarray: variable states at each step
start	end	appended value	product before -> after	best before -> after
seed	—	2	—	2
0 (reset 1)	0	2	1 -> 2	2 -> 2
0	1	3	2 -> 6	2 -> 6
0	2	-2	6 -> -12	6 -> 6
0	3	4	-12 -> -48	6 -> 6
1 (reset 1)	1	3	1 -> 3	6 -> 6
1	2	-2	3 -> -6	6 -> 6
1	3	4	-6 -> -24	6 -> 6
2 (reset 1)	2	-2	1 -> -2	6 -> 6
2	3	4	-2 -> -8	6 -> 6
3 (reset 1)	3	4	1 -> 4	6 -> 6
return	—	—	—	6

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

For n elements the inner loops perform exactly n(n + 1)/2 product extensions, with constant work each. Only indices, the running product and the best are stored; no subarrays or copies are allocated and the numeric output is constant-sized. Every intermediate product is itself a contiguous subarray product, so the stated guarantee makes Java int safe and JavaScript Number exact. Python integer sizes stay bounded by the same guarantee. Input is unchanged.

Code

Solution.java

1class Solution {2    public int maxProduct(int[] nums) {3        int best = nums[0];4        for (int i = 0; i < nums.length; i++) {5            // Each extension is a contiguous product covered by the 32-bit bound.6            int product = 1;7            for (int j = i; j < nums.length; j++) {8                product *= nums[j];9                best = Math.max(best, product);10            }11        }12        return best;13    }14}

Hints

Hint 1

Sums only need the best so far, but products need the worst too, because one more negative flips worst into best.

Hint 2

At each value the new extremes come from three candidates: the value alone, or the value times either previous extreme.

Hint 3

Snapshot the previous maximum before overwriting it so the minimum update still reads the old pair.

Edge Cases

A lone negative like [-3] returns -3; skipping is impossible since blocks are non-empty.
Zeros reset both extremes; the block after a zero restarts cleanly from the value alone.
Two negatives such as [-2, -3] multiply into the positive answer 6.
A long sequence of ones or alternating -1 values is valid at maximum length and keeps products bounded.
A negative multiplied by a previous negative minimum can become the global best, as [-2, 3, -4] shows.

Common Mistakes and Interview Tips

Tracking only the maximum misses sign flips where the previous minimum times a negative is the true best.
Overwriting curMax before computing curMin feeds the new extreme into the old pair; use a temporary.
Resetting the best at zeros instead of letting the value-alone candidate handle the restart.
Using Python nums[1:] creates an O(n) copy even though the recurrence needs only constant space; iterate by index.
Assuming only full-array prefix or suffix products are bounded does not justify int arithmetic across zero-separated blocks. The actual constraint bounds every subarray product.
Interview tip: distinguish the best ending here from the best anywhere; the answer in Example 1 ends before the final element.

Key Takeaway

When an update can invert order, carry both extremes forward: the minimum is the future maximum one sign flip away.