Maximum Product Subarray

MediumKadane’s Algorithm · Max/Min DP🧩 Kadane's Running Best LeetCode #152 ↗Updated Oct 30, 2026

Problem

Given an integer array nums containing positives, negatives and zeros, find the non-empty contiguous block whose elements multiply to the largest product, and return that product.

Input[2,3,-2,4]Output6 ([2,3])

Input[-2,0,-1]Output0

Input[-2,3,-4]Output24

1 ≤ n ≤ 2·10⁴ · -10 ≤ nums[i] ≤ 10 · every subarray product fits in a 32-bit int

Try it yourself

Java

class Solution {
    public int maxProduct(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A negative number turns the smallest product into the largest. So track both the max and the min product ending at each index; a zero simply resets both.

PatternKadane's Running Best

Instinct Best sum or product of a contiguous subarray in one pass? At each index choose - extend the run ending here or restart - and track the global best.

Memory hack Carry the bag only while it helps - a negative past is dead weight, drop it and restart here.

Open the Kadane's Running Best guide →

Approaches

Brute ForceAll Subarrays, Running Product

Time O(n²)Space O(1)

Fix each start i, extend j and multiply a running product by nums[j], so each subarray is evaluated in O(1). Keep the largest product seen.

Java

public int maxProduct(int[] nums) {
    int maxProduct = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int product = 1;
        for (int j = i; j < nums.length; j++) {
            product *= nums[j]; // product of nums[i..j]
            maxProduct = Math.max(maxProduct, product);
        }
    }
    return maxProduct;
}

Straightforward, but quadratic — too slow for n = 2·10⁴ in many judges.

BetterDP Tables (max & min ending here)

Time O(n)Space O(n)

hi[i] / lo[i] = largest / smallest product of a subarray ending at i. Each is one of three candidates: nums[i] alone, hi[i-1]·nums[i] or lo[i-1]·nums[i]. Answer = max of hi[].

Java

public int maxProduct(int[] nums) {
    int n = nums.length;
    int[] hi = new int[n], lo = new int[n];
    hi[0] = lo[0] = nums[0];
    int best = nums[0];
    for (int i = 1; i < n; i++) {
        int x = nums[i], a = hi[i - 1] * x, b = lo[i - 1] * x;
        hi[i] = Math.max(x, Math.max(a, b));
        lo[i] = Math.min(x, Math.min(a, b));
        best = Math.max(best, hi[i]);
    }
    return best;
}

Linear and easy to verify, but keeps two arrays where two variables suffice.

OptimalRolling Max/Min (Kadane Variant)

Time O(n)Space O(1)

Only the previous hi/lo are needed, so roll them in two variables. When x < 0, swap them first: multiplying by a negative makes the old min the new max candidate. Then max = max(x, max·x), min = min(x, min·x).

Java

public int maxProduct(int[] nums) {
    int maxEnd = nums[0], minEnd = nums[0], best = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int x = nums[i];
        if (x < 0) { int tmp = maxEnd; maxEnd = minEnd; minEnd = tmp; } // sign flip
        maxEnd = Math.max(x, maxEnd * x);
        minEnd = Math.min(x, minEnd * x);
        best = Math.max(best, maxEnd);
    }
    return best;
}

Dry run[2,3,-2,4,-1]

i i changed

i=0
2
i
3

-2

4

-1

max=2, min=2, best=2
i=1
2

3
i
-2

4

-1

max=6, min=3, best=6
i=2
2

3

-2
i
4

-1

swap; max=-2, min=-12
i=3
2

3

-2

4
i
-1

max=4, min=-48
i=4
2

3

-2

4

-1
i
swap; max=48 → best=48 ✔

Single pass, constant space — the expected answer.

Pro tip

Alternative O(1) trick: the answer is the max over all prefix and suffix products (restart after each 0) — scan both ways.

At a glance

Level	Approach	Time	Space
Brute Force	All Subarrays, Running Product	`O(n²)`	`O(1)`
Better	DP Tables (max & min ending here)	`O(n)`	`O(n)`
Optimal	Rolling Max/Min (Kadane Variant)	`O(n)`	`O(1)`

Common pitfalls

Tracking only the max (plain Kadane) — [-2,3,-4] gives 3 instead of 24.
Updating max then using the new max to compute min — save it first or swap.
Initialising best = 0 — wrong for [-3].

Interview tips

Start from Maximum Subarray, then show the counter-example that breaks plain Kadane.
Explain zeros: they make both max and min collapse to x, i.e. a restart.
Mention overflow: use long/double if products are not guaranteed to fit.

Pattern

Kadane with dual state (max & min) → contiguous optimum where a sign flip can swap best and worst.

My notes saved in this browser