Blind 75 Visualized

#56 · 1D DP

Maximum Product Subarray

Given an integer array, find a contiguous non-empty subarray with the largest product and return that product.

MediumLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Running product with two extremes

For each position keep both the largest and the smallest product of a subarray ending there. A negative number turns the smallest (most negative) product into the largest, so tracking only the maximum, as in the maximum-sum problem, is not enough.

Memory layout

Two numbers (curMax, curMin) plus the answer.

OperationCost
timeO(n)
spaceO(1)

Prefix and suffix products

Without zeros, the optimal subarray is either a prefix or a suffix of the array (an odd number of negatives is removed by dropping the first or last negative and everything beyond it). A zero splits the array into independent parts, so the running product restarts after it.

Memory layout

Two running products and the answer.

OperationCost
time / spaceO(n) / O(1)

Why it fits

  • Product (unlike sum) is not monotone: multiplying by a negative reverses order, so the best ending at i can come from the worst ending at i − 1.
  • A subarray ending at i either starts at i or extends one ending at i − 1, so the best and worst products ending at i follow from those at i − 1: a one-dimensional DP.
  • The sign structure also yields the prefix/suffix shortcut: the best subarray in a zero-free segment always reaches one of its two ends.

Why alternatives degrade

Kadane with only a running maximum:
For [2, -5, -2, -4, 3] the maximum after -5 is -5, which looks useless, but -5 × -2 is positive: the minimum was the important quantity.
Logarithms (sum of logs):
Logs turn products into sums but cannot handle zero or negative numbers.
Dividing the total product:
Division fails with zeros and does not choose the best contiguous subarray.

Four approaches, from naive to production

1 · beginner

Every subarray, multiply it out

time O(n³)space O(1)

For each pair (i, j) multiply nums[i..j] from scratch and keep the largest product.

int maxProduct(vector<int>& nums) {
    int best = nums[0];
    for (int i = 0; i < (int)nums.size(); i++) {
        for (int j = i; j < (int)nums.size(); j++) {
            int product = 1;
            for (int k = i; k <= j; k++) product *= nums[k];
            best = max(best, product);
        }
    }
    return best;
}

Flaws & bottlenecks

  • Every subarray is multiplied from the beginning even though neighbours share almost all of their elements.
  • Three nested loops.
  • Products can overflow 32-bit integers for long arrays (the problem guarantees the answer fits).

Interviewer cross-questions

What is repeated?

Say: The product of [i..j+1] is the product of [i..j] times one more element, yet it is recomputed from scratch.

How many subarrays are there?

Say: n(n + 1)/2. Computing each product costs up to n multiplications.

How do you avoid the inner loop?

Say: Keep a running product while extending j, which gives O(n²).

2 · intermediate

Running product from each start

time O(n²)space O(1)

For each start i keep a running product and extend j one element at a time, updating the best after each extension.

int maxProduct(vector<int>& nums) {
    int best = nums[0];
    for (int i = 0; i < (int)nums.size(); i++) {
        int product = 1;
        for (int j = i; j < (int)nums.size(); j++) {
            product *= nums[j];
            best = max(best, product);
        }
    }
    return best;
}

Flaws & bottlenecks

  • Still quadratic: for each start it re-walks the rest of the array.
  • A zero makes the running product stay 0 until the end of the inner loop, wasting work.
  • For arrays of 100,000 elements, n² is too slow.

Interviewer cross-questions

Why does one pass of the inner loop cover all subarrays starting at i?

Say: Extending j by one multiplies the running product by nums[j], giving the product of nums[i..j] in O(1).

What is the weakness?

Say: Different starts repeat the same multiplications on the tail. A DP over "best and worst ending here" removes that repetition.

How does a zero behave?

Say: Once the product hits 0 it stays 0 for every longer subarray from that start, so the rest of the inner loop is pointless.

3 · advanced

DP: best and worst product ending here

time O(n)space O(1)

At each element the new best (and worst) product ending there is the max (min) of: the element alone, the old best times it, the old worst times it. Update the global answer with the new best.

int maxProduct(vector<int>& nums) {
    int curMax = nums[0], curMin = nums[0], best = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        int x = nums[i];
        int a = curMax * x, b = curMin * x;
        curMax = max({x, a, b});
        curMin = min({x, a, b});
        best = max(best, curMax);
    }
    return best;
}

Flaws & bottlenecks

  • Needs both a maximum and a minimum, which is non-obvious (people first try only the maximum).
  • Both a and b must be computed before either curMax or curMin is overwritten.
  • A zero resets everything, which the max/min with x handles but is easy to overlook.

Interviewer cross-questions

Why track the minimum?

Say: A very negative product multiplied by a new negative number becomes very positive, so the old minimum can create the new maximum.

What happens at a zero?

Say: At a zero both extended products are 0, so curMax and curMin become 0. At the next element the old values contribute only 0, so the element itself (the "start fresh" candidate) takes over.

Why include x itself among the candidates?

Say: The best subarray ending here might start here. That covers restarts after a zero or after a product that has become worse than the element alone.

4 · expert

Prefix and suffix products, one loop

time O(n)space O(1)

Walk from both ends at once, keeping the product from the left and the product from the right, restarting a run after a zero. The best of all those products is the answer, because a best subarray always reaches one of the ends of its zero-free segment.

int maxProduct(vector<int>& nums) {
    int best = nums[0], prefix = 1, suffix = 1;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        prefix = (prefix == 0 ? 1 : prefix) * nums[i];
        suffix = (suffix == 0 ? 1 : suffix) * nums[n - 1 - i];
        best = max({best, prefix, suffix});
    }
    return best;
}

Flaws & bottlenecks

  • The correctness argument (touching an end of the segment) is subtle to explain.
  • Relies on the answer being the product of a zero-free segment or 0; the zero reset must be exactly right.
  • Does not say which subarray gives the product without extra tracking.

Interviewer cross-questions

Why must the best subarray touch an end of its zero-free segment?

Say: If the product of the whole segment is positive it is the best (all absolute values are at least 1). If it is negative, dropping the part up to and including the first negative, or from the last negative to the end, makes the product positive, and that is a prefix or suffix.

Why reset after a zero?

Say: A subarray containing a zero has product 0. After a zero the segments on either side are independent, so a fresh product starts at the next element.

Is a single element handled?

Say: Yes: best starts at nums[0], and every prefix and suffix of length 1 is included, so an array like [-3] returns -3.

Synchronized code walkthrough

Showing: Every subarray, multiply it out — shares the player above; click any step to jump.

int maxProduct(vector<int>& nums) {
    int best = nums[0];
    for (int i = 0; i < (int)nums.size(); i++) {
        for (int j = i; j < (int)nums.size(); j++) {
            int product = 1;
            for (int k = i; k <= j; k++) product *= nums[k];
            best = max(best, product);
        }
    }
    return best;
}