☕ DSA Java Articles

Topics › Arrays › Hard

Max Product Subarray

Hard TUF ID 2759 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

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

Constraints: 1 ≤ n ≤ 2 × 10^4, -10 ≤ nums[i] ≤ 10, and the product of any subarray is guaranteed to fit in a 32-bit signed integer.

Example 1

nums = [2, 3, -2, 4]
answer = 6          // [2, 3]; every subarray that contains the lone -2 is negative

Example 2

nums = [-2, 0, -1]
answer = 0          // [-2, -1] is not contiguous, so the single 0 is the best choice

Example 3

nums = [-2, 3, -4]
answer = 24         // the whole array: the two negatives cancel

What makes this harder than the maximum sum subarray is the sign. A large negative product is bad now but becomes the best possible value as soon as another negative number arrives.

Approach 1: Brute force, every subarray

Intuition. Try every subarray. Fixing the start i and extending the end j one step at a time lets us update the product with a single multiplication, so we never recompute a product from scratch. (Recomputing each product separately would cost O(n^3).)

Algorithm.

  1. For every start i: set prod = 1.
  2. For every end j ≥ i: prod *= nums[j], then update best.
  3. Return best.

best starts at Integer.MIN_VALUE, not 0: for [-2] the only subarray has product -2.

static int bruteForce(int[] nums) {
    int best = Integer.MIN_VALUE;
    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^2): about 2 × 10^8 multiplications for n = 2 × 10^4, too slow. Space O(1).

Approach 2: Optimal, prefix and suffix products

Intuition. Two observations remove almost all candidates.

  1. Zeros split the array. Any subarray containing a zero has product 0, so the interesting subarrays live inside the zero-free blocks between zeros, and 0 itself is one more candidate.
  2. Inside a zero-free block, wider is never smaller in absolute value, because every element is a non-zero integer with |x| ≥ 1. So we want the widest stretch whose sign is positive. If the block has an even number of negatives, the whole block is positive and best. If it has an odd number, we must drop exactly one negative: either the last negative and everything after it are cut away (leaving a prefix), or the first negative and everything before it are cut away (leaving a suffix).

Either way, the best subarray is a prefix or a suffix of some zero-free block. Scanning left to right with a running product gives every prefix; scanning right to left gives every suffix. When a running product hits 0, the block ended, so the next element starts a new product from 1.

Algorithm.

  1. prefix = suffix = 1, best = MIN_VALUE.
  2. For i = 0 .. n - 1: reset either product to 1 if it is 0; multiply prefix by nums[i] and suffix by nums[n - 1 - i]; update best with both.
static int prefixSuffix(int[] nums) {
    int n = nums.length, best = Integer.MIN_VALUE, prefix = 1, suffix = 1;
    for (int i = 0; i < n; i++) {
        if (prefix == 0) prefix = 1;                       // a zero ends the block; start a new one
        if (suffix == 0) suffix = 1;
        prefix *= nums[i];
        suffix *= nums[n - 1 - i];
        best = Math.max(best, Math.max(prefix, suffix));
    }
    return best;
}

Dry run on nums = [2, -5, -2, -4, 3] (three negatives, so one must go):

i nums[i] prefix nums[n-1-i] suffix best
0 2 2 3 3 3
1 -5 -10 -4 -12 3
2 -2 20 -2 24 24
3 -4 -80 -5 -120 24
4 3 -240 2 -240 24

The answer 24 is the suffix [-2, -4, 3], which drops the first negative.

Complexity. Time O(n), one pass. Space O(1). Observation 2 depends on the values being integers; with fractions such as 0.5, widening can shrink the product, and only the next approach still works.

Approach 3: Optimal, Kadane-style DP with a maximum and a minimum

Intuition. Kadane’s algorithm for sums keeps the best sum of a subarray ending at the current index. For products that single value is not enough. The smallest (most negative) product ending at i - 1, multiplied by a negative nums[i], may become the largest. So keep two states:

Every subarray ending at i is either [nums[i]] alone or a subarray ending at i - 1 extended by nums[i]. If x = nums[i] ≥ 0, multiplying by x keeps the order, so the largest extension is maxEnd · x and the smallest is minEnd · x. If x < 0, the order flips: the largest extension is minEnd · x. Swapping the two values before multiplying handles both cases with the same two lines. A zero sets both states to 0, which restarts the scan automatically.

Algorithm.

  1. maxEnd = minEnd = best = nums[0].
  2. For each later x: if x < 0, swap maxEnd and minEnd. Then maxEnd = max(x, maxEnd · x), minEnd = min(x, minEnd · x), and best = max(best, maxEnd).
static int minMaxDp(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) {                                       // multiplying by a negative swaps largest and smallest
            int t = maxEnd;
            maxEnd = minEnd;
            minEnd = t;
        }
        maxEnd = Math.max(x, maxEnd * x);                  // either start fresh at x or extend
        minEnd = Math.min(x, minEnd * x);
        best = Math.max(best, maxEnd);
    }
    return best;
}

Dry run on Example 1, nums = [2, 3, -2, 4]:

i x swap? maxEnd minEnd best
0 2 start 2 2 2
1 3 no max(3, 6) = 6 min(3, 6) = 3 6
2 -2 yes, max = 3, min = 6 max(-2, -6) = -2 min(-2, -12) = -12 6
3 4 no max(4, -8) = 4 min(4, -48) = -48 6

Complexity. Time O(n), space O(1). This version does not rely on |x| ≥ 1, so it also works for real numbers.

Edge cases and pitfalls