107.Maximum Product Subarray

MediumBlind 751-D Dynamic Programming · 9/12

Problem

Given an integer array nums, find the contiguous, non-empty subarray whose elements have the largest product, and return that product.

The values can be negative or zero, and the answer is guaranteed to fit in a 32-bit integer.

Examples

Input:  nums = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] has product 6.

Input:  nums = [-2, 0, -1]
Output: 0
Explanation: [-2, -1] is not contiguous, so the best is [0].

Input:  nums = [-2, 3, -4]
Output: 24
Explanation: The whole array: two negatives make a positive.

Constraints

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
The product of any subarray fits in a 32-bit integer.

💡 Key Insight

With sums (Kadane), the best subarray ending at i only needs the best ending at i - 1. With products, a negative number flips the order: the smallest (most negative) product ending at i - 1, multiplied by a negative nums[i], may become the largest. So track both: maxEnd(i) = max(nums[i], nums[i]·maxEnd(i-1), nums[i]·minEnd(i-1)) and minEnd(i) = min(nums[i], nums[i]·maxEnd(i-1), nums[i]·minEnd(i-1)). The nums[i] option alone lets a zero "reset" the run. The answer is the max of maxEnd(i) over all i, and only the previous pair is needed — O(n) time, O(1) space.

Brute Force

TimeO(n²)SpaceO(1).

Intuition

Try every start i, extend the end j one step at a time while maintaining the running product, and keep the best product seen.

Algorithm

best = nums[0].
For each i: prod = 1; for j = i..n-1: prod *= nums[j], best = max(best, prod).
Return best.

Visualization

nums = [2, 3, -2, 4]
i=0: 2, 6, -12, -48     best so far 6
i=1: 3, -6, -24         best 6
i=2: -2, -8             best 6
i=3: 4                  best 6

Code

java

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

Complexity

Time: O(n²) — every subarray, with O(1) incremental product.
Space: O(1).

Top-Down Memoization

TimeO(n)SpaceO(n)

Intuition

Define hi(i) and lo(i) = the largest / smallest product of a subarray ending exactly at i. Each depends only on hi(i - 1) and lo(i - 1). Written naively as two mutually recursive functions, hi(i) calls both hi(i-1) and lo(i-1), and so does lo(i) — the call tree doubles at every level. Caching each (i, kind) pair collapses it to 2n states.

Recurrence: hi(i) = max(nums[i], nums[i]·hi(i-1), nums[i]·lo(i-1)), lo(i) = min(nums[i], nums[i]·hi(i-1), nums[i]·lo(i-1)), with hi(0) = lo(0) = nums[0]. Answer: max over i of hi(i).

Algorithm

Integer[] memoHi, memoLo of size n.
hi(i) / lo(i): base i == 0 → nums[0]; otherwise compute from hi(i-1) and lo(i-1) and cache.
Return max(hi(i)) over all i.

Visualization

nums = [2, 3, -2]. Without caching, hi(0) / lo(0) are evaluated four times.

flowchart TD
    A["hi(2)"] --> B["hi(1)"]
    A --> C["lo(1)"]
    L["lo(2)"] --> B2["hi(1) again"]
    L --> C2["lo(1) again"]
    B --> D["hi(0) = 2"]
    B --> E["lo(0) = 2"]
    C --> F["hi(0) = 2"]
    C --> G["lo(0) = 2"]

With the cache: hi(1) = max(3, 3·2, 3·2) = 6, lo(1) = min(3, 6, 6) = 3, then hi(2) = max(-2, -2·6, -2·3) = -2 and lo(2) = -12. The second hi(1) / lo(1) calls are cache hits.

Answer max(hi(0), hi(1), hi(2)) = max(2, 6, -2) = 6.

Code

java

class Solution {
    private Integer[] memoHi, memoLo;
    private int[] nums;

    public int maxProduct(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        memoHi = new Integer[n];
        memoLo = new Integer[n];
        int best = nums[0];
        for (int i = 0; i < n; i++) {
            best = Math.max(best, hi(i));
        }
        return best;
    }

    // largest product of a subarray ending at i
    private int hi(int i) {
        if (i == 0) {
            return nums[0];
        }
        if (memoHi[i] != null) {
            return memoHi[i];
        }
        int a = nums[i] * hi(i - 1), b = nums[i] * lo(i - 1);
        memoHi[i] = Math.max(nums[i], Math.max(a, b));
        return memoHi[i];
    }

    // smallest product of a subarray ending at i
    private int lo(int i) {
        if (i == 0) {
            return nums[0];
        }
        if (memoLo[i] != null) {
            return memoLo[i];
        }
        int a = nums[i] * hi(i - 1), b = nums[i] * lo(i - 1);
        memoLo[i] = Math.min(nums[i], Math.min(a, b));
        return memoLo[i];
    }
}

Complexity

Time: O(n) — 2n cached states, O(1) each.
Space: O(n) — two memo arrays. The main loop asks for hi(0), hi(1), ... in order, so each call finds i - 1 already cached and the recursion stays shallow; calling hi(n - 1) cold would recurse n deep.

Bottom-Up Tabulation

TimeO(n).SpaceO(n)

Intuition

Fill maxDp[i] and minDp[i] left to right — no recursion needed, since each entry reads only index i - 1.

Algorithm

maxDp[0] = minDp[0] = best = nums[0].
For i = 1..n-1:
- a = nums[i] * maxDp[i-1], b = nums[i] * minDp[i-1].
- maxDp[i] = max(nums[i], a, b), minDp[i] = min(nums[i], a, b).
- best = max(best, maxDp[i]).
Return best.

Dry Run

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

i	0	1	2	3	4
nums[i]	2	3	-2	4	-1
maxDp	2	6	-2	4	48
minDp	2	3	-12	-48	-4

At i = 4: -1 × minDp[3] = -1 × -48 = 48 — the stored minimum became the new maximum (whole array).

Code

java

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] maxDp = new int[n];
        int[] minDp = new int[n];
        maxDp[0] = minDp[0] = nums[0];
        int best = nums[0];
        for (int i = 1; i < n; i++) {
            int a = nums[i] * maxDp[i - 1];
            int b = nums[i] * minDp[i - 1];
            maxDp[i] = Math.max(nums[i], Math.max(a, b)); // nums[i] alone = restart
            minDp[i] = Math.min(nums[i], Math.min(a, b));
            best = Math.max(best, maxDp[i]);
        }
        return best;
    }
}

Complexity

Time: O(n).
Space: O(n) — two arrays.

Space-Optimized DPOptimal

TimeO(n)SpaceO(1).

Intuition

Only the previous max/min pair is ever read, so keep two variables. Compute both new values from the old pair before overwriting (use a temp), exactly like Kadane's algorithm extended with a running minimum.

Algorithm

curMax = curMin = best = nums[0].
For i = 1..n-1:
- a = nums[i] * curMax, b = nums[i] * curMin.
- curMax = max(nums[i], a, b), curMin = min(nums[i], a, b).
- best = max(best, curMax).
Return best.

Dry Run

flowchart LR
    A["x=-2<br/>max=-2, min=-2"] -->|"x=3"| B["max = max(3, -6, -6) = 3<br/>min = -6"]
    B -->|"x=-4"| C["max = max(-4, -12, 24) = 24<br/>min = -12"]
    C --> D["best = 24"]

Code

java

class Solution {
    public int maxProduct(int[] nums) {
        int curMax = nums[0]; // largest product ending at the current index
        int curMin = nums[0]; // smallest (most negative) product ending here
        int best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            int a = x * curMax;
            int b = x * curMin;
            // compute both from the old pair: a negative x swaps their roles
            curMax = Math.max(x, Math.max(a, b));
            curMin = Math.min(x, Math.min(a, b));
            best = Math.max(best, curMax);
        }
        return best;
    }
}

Complexity

Time: O(n) — single pass.
Space: O(1).

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Top-Down Memoization	O(n)	O(n)
Bottom-Up Tabulation	O(n)	O(n)
Space-Optimized DP	O(n)	O(1)

Common Pitfalls

Tracking only the maximum — [-2, 3, -4] needs the stored minimum -6 to reach 24.
Updating curMax first and then using the new curMax to compute curMin; save the old values (or the products) first.
Initialising best = 0 — an all-negative single element like [-3] must return -3.
Forgetting the "start fresh at nums[i]" option, which is what lets a 0 break the run.