Loading…

mediumDynamic ProgrammingLC #152Frequently asked

Maximum Product Subarray

Q: How do you solve Maximum Product Subarray using the Brute Force — Every Subarray Product approach?

When to use it: State it to set the O(n²) baseline and to make the redundant re-multiplication obvious before optimizing. For every start index `i`, extend the end `j` to the right, keeping a running product, and update the global maximum at each step. **Why it's the right baseline to state.** The problem is 'best over all contiguous subarrays', and the no-insight version enumerates all of them. By carrying a running product as `j` advances (rather than recomputing the whole product each time), each subarray costs O(1) to evaluate, so the total is O(n²) — quadratic, not cubic. Saying this out loud shows you can optimize *within* brute force before reaching for the linear trick. **What it reveals.** Watch what happens at a sign change: extending across a negative number can turn a large positive running product into a large negative one — and extending again across another negative flips it back to large positive. Brute force 'sees' this only because it tries every start independently. The O(n) solution has to *remember* that flip with a single carried value, which motivates tracking the running minimum. **Why we don't ship it.** For n = 2 × 10⁴, O(n²) is 4 × 10⁸ operations — sluggish and a signal you didn't spot the linear structure. Mention it, give the bound, then move to the one-pass max/min scan. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Maximum Product Subarray using the One Pass — Track Max AND Min (Optimal) approach?

When to use it: The answer they want. Lead with the insight: 'a negative number turns the smallest product into the largest, so I carry both.' Carry two values as you scan: `curMax` and `curMin`, the largest and smallest products of a subarray *ending at the current index*. Update the global `best` from `curMax` each step. **Why one running value isn't enough.** Kadane's max-sum keeps only the running maximum because addition is order-preserving: if `a ≥ b` then `a + x ≥ b + x`, so the best prefix stays the best. Multiplication breaks this. Multiply by a negative `x` and the inequality *reverses*: the smallest (most negative) product suddenly becomes the largest. So the candidate for 'best ending here' might come from the *worst* product ending one step back. The fix is to remember both extremes. **The update, and why the swap.** At each element the new `curMax` is the best of three options: start fresh at `nums[i]`, extend the previous max (`curMax * nums[i]`), or extend the previous min (`curMin * nums[i]`). When `nums[i] < 0`, multiplying flips which of the previous two is bigger — so we **swap** `curMax` and `curMin` before applying `curMax = max(nums[i], curMax * nums[i])` and `curMin = min(nums[i], curMin * nums[i])`. The swap is just a clean way to keep the formulas the same regardless of sign. **Why the fresh-start term handles zeros for free.** Including `nums[i]` itself in the max/min (not only the extended products) means that after a zero — which forces both `curMax` and `curMin` to 0 — the next element restarts the subarray at itself rather than being stuck multiplying by 0. No special-casing of zero is needed; the `max(nums[i], …)` term *is* the restart. **Seeding.** Initialize all three from `nums[0]` and iterate from index 1. Seeding `best` from 0 or 1 is a classic bug — it makes all-negative or single-negative inputs wrong (the answer can legitimately be negative). Time complexity: O(n). Space complexity: O(1).

LCPractice

Dynamic Programming · 13 of 44 · 8 min

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 answer fits in a 32-bit integer.

A subarray is a contiguous, non-empty sequence of elements within an array.

In plain English

Slide a window of contiguous elements and maximize their product. The catch versus max-sum is the sign: two negatives multiply to a positive, and a single zero resets everything. So 'the best ending here' can come from the *worst* ending one step back.

Examples

Example 1

Input: nums = [2, 3, -2, 4]
Output: 6
Note: The subarray [2, 3] has product 6. The -2 then 4 can't beat it because of the lone negative.

Example 2

Input: nums = [-2, 0, -1]
Output: 0
Note: Any subarray spanning the 0 is 0; the best non-zero options (-2, -1) are negative, so 0 wins.

Example 3

Input: nums = [-2, 3, -4]
Output: 24
Note: The whole array: -2 × 3 × -4 = 24. The two negatives multiply to a positive — only tracking the min captures this.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
The product of any prefix is guaranteed to fit in a 32-bit integer
The subarray must be contiguous and non-empty

Clarifying questions4First question: Can the array contain negative numbers?Explore questions

Q1.Can the array contain negative numbers?
Yes — that's the whole point. Two negatives make a positive, so the running minimum can become the maximum after a negative.
Q2.Can it contain zeros?
Yes. A zero resets the product; the cleanest handling is to allow starting a new subarray at nums[i], which naturally recovers after a zero.
Q3.Is the subarray contiguous?
Yes, contiguous and non-empty. If subsequences were allowed it would be a different problem.
Q4.Could the product overflow?
The problem guarantees the answer fits in 32 bits, so in Java I don't need long. In Python integers are arbitrary precision anyway.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the contiguous subarray with the largest product. Unlike Kadane's max-sum, you must track BOTH the running max AND the running min ending here — because a negative number flips the smallest (most-negative) product into the largest. One pass, swap max/min when the current number is negative, O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize plain Kadane fails on products because negatives invert ordering — and whether you fix it by carrying the running minimum alongside the maximum.

Where candidates slip

Tracking only the max (Kadane for sums) and getting [-2, 3, -4] wrong, or mishandling zeros by not allowing a fresh restart at nums[i].

How to stand out

State the negative-flips-sign insight explicitly, handle zeros via the max(nums[i], …) reset rather than a special case, and collapse to O(1) space with two scalars.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Every Subarray Product	`O(n²)`	`O(1)`	State it to set the O(n²) baseline and to make the redundant re-multiplication obvious before optimizing.	Read
2	One Pass — Track Max AND Min (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Lead with the insight: 'a negative number turns the smallest product into the largest, so I carry both.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMax contiguous SUBARRAYCombine op?SumProductExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Every Subarray Product

TimeO(n²)SpaceO(1)

State it to set the O(n²) baseline and to make the redundant re-multiplication obvious before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The literal task is 'largest product over all contiguous subarrays'. How many subarrays are there, and how do you get each product cheaply?

2Hint 2Explore hint

Fix a start i, then extend an end j rightward, multiplying nums[j] into a running product as you go. Track the global max.

3Hint 3Explore hint

Two nested loops: outer over start i, inner over end j ≥ i carrying the product. ~n²/2 subarrays, O(1) per extension.

A · Core idea

For every start index i, extend the end j to the right, keeping a running product, and update the global maximum at each step.

Why it's the right baseline to state. The problem is 'best over all contiguous subarrays', and the no-insight version enumerates all of them. By carrying a running product as j advances (rather than recomputing the whole product each time), each subarray costs O(1) to evaluate, so the total is O(n²) — quadratic, not cubic. Saying this out loud shows you can optimize within brute force before reaching for the linear trick.

What it reveals. Watch what happens at a sign change: extending across a negative number can turn a large positive running product into a large negative one — and extending again across another negative flips it back to large positive. Brute force 'sees' this only because it tries every start independently. The O(n) solution has to remember that flip with a single carried value, which motivates tracking the running minimum.

Why we don't ship it. For n = 2 × 10⁴, O(n²) is 4 × 10⁸ operations — sluggish and a signal you didn't spot the linear structure. Mention it, give the bound, then move to the one-pass max/min scan.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

j=1

product = 2×3 = 6

i ↓

[0]

j ↓

[1]

-2

[2]

[3]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

Reference implementation previewpublic int maxProduct(int[] nums) { int best = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { int product = 1; for (int j = i; j < nums.length; j++) {Explore the full code

solution.javaJava

Brute Force — Every Subarray Product — reference

3 teaching notes

1
public int maxProduct(int[] nums) {
2
    int best = Integer.MIN_VALUE;
3
    for (int i = 0; i < nums.length; i++) {
4
        // Reset the running product for each new start index i.
5
        int product = 1;
6
        for (int j = i; j < nums.length; j++) {
7
            // Extend the subarray by one element in O(1) instead of recomputing the
8
            // whole product.
9
            product *= nums[j];
10
            // Every prefix from i to j is a candidate subarray.
11
            best = Math.max(best, product);
12
        }
13
    }
14
    return best;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Re-multiplying from scratch for each (i, j) would be O(n³); carrying the product as you extend the end makes it O(n²). That 'carry the partial result' move is itself a mini-DP, and it's the gateway to realizing you can carry just one or two values across the whole array.

ComplexityO(n²) time, O(1) space — n start positions × up to n extensions each, O(1) multiply per step → O(n²) time. Only a running product and a global max → O(1) space.

E · Edge cases and pitfalls4nums = [-3] — Single subarray, product = -3; best = -3. Confirms non-empty and seeding from MIN_VALUE.Explore edge cases

Edge cases handled

nums = [-3]Single subarray, product = -3; best = -3. Confirms non-empty and seeding from MIN_VALUE.

Pitfalls

Initializing best to 0 — wrong when every subarray is negative (e.g. [-3]).
Recomputing the full product for each (i, j) — turns O(n²) into O(n³).
Forgetting that the inner product can legitimately be negative; don't clamp it.

03.2

Approach 2 of 2 · Optimal

One Pass — Track Max AND Min (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Lead with the insight: 'a negative number turns the smallest product into the largest, so I carry both.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Kadane works for sums because a bigger running sum is always at least as useful. Why does that reasoning fail for products?

2Hint 2Explore hint

Because multiplying by a negative flips ordering: the most-negative product becomes the most-positive. So the running MINIMUM matters — keep it too.

3Hint 3Explore hint

Carry curMax and curMin ending at i. When nums[i] is negative, swap them before multiplying. Always allow nums[i] alone as a fresh start (handles zeros).

A · Core idea

Carry two values as you scan: curMax and curMin, the largest and smallest products of a subarray ending at the current index. Update the global best from curMax each step.

Why one running value isn't enough. Kadane's max-sum keeps only the running maximum because addition is order-preserving: if a ≥ b then a + x ≥ b + x, so the best prefix stays the best. Multiplication breaks this. Multiply by a negative x and the inequality reverses: the smallest (most negative) product suddenly becomes the largest. So the candidate for 'best ending here' might come from the worst product ending one step back. The fix is to remember both extremes.

The update, and why the swap. At each element the new curMax is the best of three options: start fresh at nums[i], extend the previous max (curMax * nums[i]), or extend the previous min (curMin * nums[i]). When nums[i] < 0, multiplying flips which of the previous two is bigger — so we swap curMax and curMin before applying curMax = max(nums[i], curMax * nums[i]) and curMin = min(nums[i], curMin * nums[i]). The swap is just a clean way to keep the formulas the same regardless of sign.

Why the fresh-start term handles zeros for free. Including nums[i] itself in the max/min (not only the extended products) means that after a zero — which forces both curMax and curMin to 0 — the next element restarts the subarray at itself rather than being stuck multiplying by 0. No special-casing of zero is needed; the max(nums[i], …) term is the restart.

Seeding. Initialize all three from nums[0] and iterate from index 1. Seeding best from 0 or 1 is a classic bug — it makes all-negative or single-negative inputs wrong (the answer can legitimately be negative).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [-2, 3, -4]

Array state

i=1, x=3

curMax=3, curMin=-6

-2

[0]

i ↓

[1]

-4

[2]

Current pointerResolved stateNot processed

Final result24

C · Code with teaching comments

solution.javaJava

One Pass — Track Max AND Min (Optimal) — optimal

4 teaching notes

1
public int maxProduct(int[] nums) {
2
    // Seed all three from the first element — never from 0 or 1, or negatives break.
3
    int curMax = nums[0], curMin = nums[0], best = nums[0];
4
    for (int i = 1; i < nums.length; i++) {
5
        int x = nums[i];
6
        // A negative multiplier flips ordering, so the roles of max and min reverse.
7
        if (x < 0) {
8
            int tmp = curMax;
9
            curMax = curMin;
10
            curMin = tmp;
11
        }
12
        // Best ending here is either a fresh start at x or extending the previous best
13
        // — the 'x' term is the zero-reset.
14
        curMax = Math.max(x, curMax * x);
15
        curMin = Math.min(x, curMin * x);
16
        // Global answer only ever needs the running max.
17
        best = Math.max(best, curMax);
18
    }
19
    return best;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The whole trick is recognizing that with products the minimum is a latent maximum: one negative number away from becoming the best. Carry the worst case so a future sign flip can promote it. Any time a transformation can invert ordering, tracking both extremes is the move — this is the conceptual cousin of Kadane, not a separate species.

ComplexityO(n) time, O(1) space — Single pass, O(1) work per element (two multiplies, a couple of comparisons) → O(n) time. Three scalars (best, curMax, curMin) → O(1) space.

E · Edge cases and pitfalls5nums = [-2, 0, -1] — At the 0 both curMax and curMin become 0 (max(0, …)). The -1 restarts at itself. best stays 0 — the correct answer.Explore edge cases

Edge cases handled

nums = [-2, 0, -1]At the 0 both curMax and curMin become 0 (max(0, …)). The -1 restarts at itself. best stays 0 — the correct answer.
nums = [-2]Seed best = curMax = curMin = -2; loop never runs; returns -2. Why seeding from nums[0] (not 0) matters.

Pitfalls

Tracking only curMax — fails on [-2, 3, -4] (returns 3 instead of 24).
Multiplying before swapping on a negative — applies the formulas to the wrong extremes.
Seeding best/curMax/curMin to 0 or 1 instead of nums[0] — breaks all-negative and single-element inputs.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int maxProduct(int[] nums) { int curMax = nums[0], curMin = nums[0], best = nums[0]; for (int i = 1; i < nums.length; i++) { int x = nums[i]; if (x < 0) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Tracking only the maximum

Products invert under negatives, so the running minimum can become the maximum. Keeping only curMax returns 3 on [-2, 3, -4] instead of 24.

Explore the code comparison

Don't write this

cur_max = best = nums[0]
for x in nums[1:]:
    cur_max = max(x, cur_max * x)   # min never tracked
    best = max(best, cur_max)

Write this instead

cur_max = cur_min = best = nums[0]
for x in nums[1:]:
    if x < 0:
        cur_max, cur_min = cur_min, cur_max
    cur_max = max(x, cur_max * x)
    cur_min = min(x, cur_min * x)
    best = max(best, cur_max)

Multiplying before swapping

On a negative element the max and min roles reverse. If you multiply first and swap after, curMax and curMin are computed from the wrong predecessors.

Explore the code comparison

Don't write this

curMax = Math.max(x, curMax * x);
curMin = Math.min(x, curMin * x);
if (x < 0) { int t = curMax; curMax = curMin; curMin = t; }

Write this instead

if (x < 0) { int t = curMax; curMax = curMin; curMin = t; }
curMax = Math.max(x, curMax * x);
curMin = Math.min(x, curMin * x);

Wrong seed value

Seeding best to 0 makes all-negative arrays return 0; seeding to 1 invents a product no subarray has. The first real element is the only correct seed.

Explore the code comparison

Don't write this

int best = 0, curMax = 1, curMin = 1;

Write this instead

int best = nums[0], curMax = nums[0], curMin = nums[0];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Kadane with a twist — carry max AND min

Code pattern to memorize

curMax = curMin = best = nums[0]
for x in nums[1:]:
    if x < 0: curMax, curMin = curMin, curMax
    curMax = max(x, curMax * x)
    curMin = min(x, curMin * x)
    best = max(best, curMax)

Rules to remember

1Track both curMax and curMin ending at i — a negative number turns the most-negative product into the most-positive.
2When nums[i] < 0, swap curMax and curMin before multiplying — the roles reverse.
3Always include nums[i] itself as a fresh start: curMax = max(nums[i], curMax * nums[i]) — this resets after a zero.
4A zero wipes both running products to 0; starting fresh at nums[i] handles it for free, no special case.
5Seed all three (best, curMax, curMin) from nums[0], then iterate from index 1 — never seed from 0 or 1.

Use this pattern when

Maximize a contiguous subarray under a non-additive op (product) where sign matters
The combine step can flip best↔worst depending on the current element
You need O(n) one-pass and the array has negatives and/or zeros
Kadane-shaped problem but the monotonicity of 'bigger is always better' breaks

Choose another pattern when

Maximize a SUM, not a product → plain Kadane, track only the max
All elements positive → it's just the whole-array product, no min needed
Subsequence (non-contiguous) allowed → different problem entirely
Need the indices/the subarray itself, not just the value → extend with bookkeeping

Interview takeaway

The insight is that with products, the worst (most negative) running value is a future champion waiting for the next negative number to flip it. Carry both extremes and a sign flip costs nothing. This 'track min too' idea recurs anywhere a transform can invert ordering.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternKadane-with-two-states. When maximizing a contiguous subarray under an operation that can invert ordering (multiplication, sign flips), carry both the running best and running worst. Sibling of Maximum Subarray; the min-tracking idea generalizes to any order-inverting transform.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Subarray
Coming soon
The additive cousin — plain Kadane, track only the running max sum (no sign flip).
Product of Array Except Self
Coming soon
Prefix and suffix products in O(n) without division — a different product trick.
Maximum Product of Three Numbers
Coming soon
Same negative-pair insight: the answer is max(top3) or (two smallest negatives × largest).
Max Length of Subarray With Positive Product
Coming soon
Track lengths of positive- and negative-product runs — a length variant of the same idea.

Same pattern

←

Longest Common Subsequence

Continue · Next problem

Edit Distance

mediumDynamic ProgrammingLC #152Frequently asked

Maximum Product Subarray

LCPractice

Dynamic Programming · 13 of 44 · 8 min

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 answer fits in a 32-bit integer.

A subarray is a contiguous, non-empty sequence of elements within an array.

In plain English

Examples

Example 1

Input: nums = [2, 3, -2, 4]
Output: 6
Note: The subarray [2, 3] has product 6. The -2 then 4 can't beat it because of the lone negative.

Example 2

Input: nums = [-2, 0, -1]
Output: 0
Note: Any subarray spanning the 0 is 0; the best non-zero options (-2, -1) are negative, so 0 wins.

Example 3

Input: nums = [-2, 3, -4]
Output: 24
Note: The whole array: -2 × 3 × -4 = 24. The two negatives multiply to a positive — only tracking the min captures this.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
The product of any prefix is guaranteed to fit in a 32-bit integer
The subarray must be contiguous and non-empty

Clarifying questions4First question: Can the array contain negative numbers?Explore questions

Q1.Can the array contain negative numbers?
Yes — that's the whole point. Two negatives make a positive, so the running minimum can become the maximum after a negative.
Q2.Can it contain zeros?
Yes. A zero resets the product; the cleanest handling is to allow starting a new subarray at nums[i], which naturally recovers after a zero.
Q3.Is the subarray contiguous?
Yes, contiguous and non-empty. If subsequences were allowed it would be a different problem.
Q4.Could the product overflow?
The problem guarantees the answer fits in 32 bits, so in Java I don't need long. In Python integers are arbitrary precision anyway.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize plain Kadane fails on products because negatives invert ordering — and whether you fix it by carrying the running minimum alongside the maximum.

Where candidates slip

Tracking only the max (Kadane for sums) and getting [-2, 3, -4] wrong, or mishandling zeros by not allowing a fresh restart at nums[i].

How to stand out

State the negative-flips-sign insight explicitly, handle zeros via the max(nums[i], …) reset rather than a special case, and collapse to O(1) space with two scalars.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Every Subarray Product	`O(n²)`	`O(1)`	State it to set the O(n²) baseline and to make the redundant re-multiplication obvious before optimizing.	Read
2	One Pass — Track Max AND Min (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Lead with the insight: 'a negative number turns the smallest product into the largest, so I carry both.'	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Every Subarray Product

TimeO(n²)SpaceO(1)

State it to set the O(n²) baseline and to make the redundant re-multiplication obvious before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The literal task is 'largest product over all contiguous subarrays'. How many subarrays are there, and how do you get each product cheaply?

2Hint 2Explore hint

Fix a start i, then extend an end j rightward, multiplying nums[j] into a running product as you go. Track the global max.

3Hint 3Explore hint

Two nested loops: outer over start i, inner over end j ≥ i carrying the product. ~n²/2 subarrays, O(1) per extension.

A · Core idea

For every start index i, extend the end j to the right, keeping a running product, and update the global maximum at each step.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

j=1

product = 2×3 = 6

i ↓

[0]

j ↓

[1]

-2

[2]

[3]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

solution.javaJava

Brute Force — Every Subarray Product — reference

3 teaching notes

1
public int maxProduct(int[] nums) {
2
    int best = Integer.MIN_VALUE;
3
    for (int i = 0; i < nums.length; i++) {
4
        // Reset the running product for each new start index i.
5
        int product = 1;
6
        for (int j = i; j < nums.length; j++) {
7
            // Extend the subarray by one element in O(1) instead of recomputing the
8
            // whole product.
9
            product *= nums[j];
10
            // Every prefix from i to j is a candidate subarray.
11
            best = Math.max(best, product);
12
        }
13
    }
14
    return best;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — n start positions × up to n extensions each, O(1) multiply per step → O(n²) time. Only a running product and a global max → O(1) space.

E · Edge cases and pitfalls4nums = [-3] — Single subarray, product = -3; best = -3. Confirms non-empty and seeding from MIN_VALUE.Explore edge cases

Edge cases handled

nums = [-3]Single subarray, product = -3; best = -3. Confirms non-empty and seeding from MIN_VALUE.

Pitfalls

Initializing best to 0 — wrong when every subarray is negative (e.g. [-3]).
Recomputing the full product for each (i, j) — turns O(n²) into O(n³).
Forgetting that the inner product can legitimately be negative; don't clamp it.

03.2

Approach 2 of 2 · Optimal

One Pass — Track Max AND Min (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Lead with the insight: 'a negative number turns the smallest product into the largest, so I carry both.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Kadane works for sums because a bigger running sum is always at least as useful. Why does that reasoning fail for products?

2Hint 2Explore hint

Because multiplying by a negative flips ordering: the most-negative product becomes the most-positive. So the running MINIMUM matters — keep it too.

3Hint 3Explore hint

Carry curMax and curMin ending at i. When nums[i] is negative, swap them before multiplying. Always allow nums[i] alone as a fresh start (handles zeros).

A · Core idea

Carry two values as you scan: curMax and curMin, the largest and smallest products of a subarray ending at the current index. Update the global best from curMax each step.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [-2, 3, -4]

Array state

i=1, x=3

curMax=3, curMin=-6

-2

[0]

i ↓

[1]

-4

[2]

Current pointerResolved stateNot processed

Final result24

C · Code with teaching comments

solution.javaJava

One Pass — Track Max AND Min (Optimal) — optimal

4 teaching notes

1
public int maxProduct(int[] nums) {
2
    // Seed all three from the first element — never from 0 or 1, or negatives break.
3
    int curMax = nums[0], curMin = nums[0], best = nums[0];
4
    for (int i = 1; i < nums.length; i++) {
5
        int x = nums[i];
6
        // A negative multiplier flips ordering, so the roles of max and min reverse.
7
        if (x < 0) {
8
            int tmp = curMax;
9
            curMax = curMin;
10
            curMin = tmp;
11
        }
12
        // Best ending here is either a fresh start at x or extending the previous best
13
        // — the 'x' term is the zero-reset.
14
        curMax = Math.max(x, curMax * x);
15
        curMin = Math.min(x, curMin * x);
16
        // Global answer only ever needs the running max.
17
        best = Math.max(best, curMax);
18
    }
19
    return best;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — Single pass, O(1) work per element (two multiplies, a couple of comparisons) → O(n) time. Three scalars (best, curMax, curMin) → O(1) space.

E · Edge cases and pitfalls5nums = [-2, 0, -1] — At the 0 both curMax and curMin become 0 (max(0, …)). The -1 restarts at itself. best stays 0 — the correct answer.Explore edge cases

Edge cases handled

nums = [-2, 0, -1]At the 0 both curMax and curMin become 0 (max(0, …)). The -1 restarts at itself. best stays 0 — the correct answer.
nums = [-2]Seed best = curMax = curMin = -2; loop never runs; returns -2. Why seeding from nums[0] (not 0) matters.

Pitfalls

Tracking only curMax — fails on [-2, 3, -4] (returns 3 instead of 24).
Multiplying before swapping on a negative — applies the formulas to the wrong extremes.
Seeding best/curMax/curMin to 0 or 1 instead of nums[0] — breaks all-negative and single-element inputs.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Tracking only the maximum

Products invert under negatives, so the running minimum can become the maximum. Keeping only curMax returns 3 on [-2, 3, -4] instead of 24.

Explore the code comparison

Don't write this

cur_max = best = nums[0]
for x in nums[1:]:
    cur_max = max(x, cur_max * x)   # min never tracked
    best = max(best, cur_max)

Write this instead

cur_max = cur_min = best = nums[0]
for x in nums[1:]:
    if x < 0:
        cur_max, cur_min = cur_min, cur_max
    cur_max = max(x, cur_max * x)
    cur_min = min(x, cur_min * x)
    best = max(best, cur_max)

Multiplying before swapping

On a negative element the max and min roles reverse. If you multiply first and swap after, curMax and curMin are computed from the wrong predecessors.

Explore the code comparison

Don't write this

curMax = Math.max(x, curMax * x);
curMin = Math.min(x, curMin * x);
if (x < 0) { int t = curMax; curMax = curMin; curMin = t; }

Write this instead

if (x < 0) { int t = curMax; curMax = curMin; curMin = t; }
curMax = Math.max(x, curMax * x);
curMin = Math.min(x, curMin * x);

Wrong seed value

Seeding best to 0 makes all-negative arrays return 0; seeding to 1 invents a product no subarray has. The first real element is the only correct seed.

Explore the code comparison

Don't write this

int best = 0, curMax = 1, curMin = 1;

Write this instead

int best = nums[0], curMax = nums[0], curMin = nums[0];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Kadane with a twist — carry max AND min

Code pattern to memorize

curMax = curMin = best = nums[0]
for x in nums[1:]:
    if x < 0: curMax, curMin = curMin, curMax
    curMax = max(x, curMax * x)
    curMin = min(x, curMin * x)
    best = max(best, curMax)

Rules to remember

1Track both curMax and curMin ending at i — a negative number turns the most-negative product into the most-positive.
2When nums[i] < 0, swap curMax and curMin before multiplying — the roles reverse.
3Always include nums[i] itself as a fresh start: curMax = max(nums[i], curMax * nums[i]) — this resets after a zero.
4A zero wipes both running products to 0; starting fresh at nums[i] handles it for free, no special case.
5Seed all three (best, curMax, curMin) from nums[0], then iterate from index 1 — never seed from 0 or 1.

Use this pattern when

Maximize a contiguous subarray under a non-additive op (product) where sign matters
The combine step can flip best↔worst depending on the current element
You need O(n) one-pass and the array has negatives and/or zeros
Kadane-shaped problem but the monotonicity of 'bigger is always better' breaks

Choose another pattern when

Maximize a SUM, not a product → plain Kadane, track only the max
All elements positive → it's just the whole-array product, no min needed
Subsequence (non-contiguous) allowed → different problem entirely
Need the indices/the subarray itself, not just the value → extend with bookkeeping

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Subarray
Coming soon
The additive cousin — plain Kadane, track only the running max sum (no sign flip).
Product of Array Except Self
Coming soon
Prefix and suffix products in O(n) without division — a different product trick.
Maximum Product of Three Numbers
Coming soon
Same negative-pair insight: the answer is max(top3) or (two smallest negatives × largest).
Max Length of Subarray With Positive Product
Coming soon
Track lengths of positive- and negative-product runs — a length variant of the same idea.

Same pattern

←

Longest Common Subsequence

Continue · Next problem

Edit Distance