A promo engine stacks consecutive day factors onto a SKU. Factors can be negative — a clawback that inverts the running product. Merchandising wants the stretch whose product is largest. The intern nested every start and end, multiplying a[i] through a[j]. A week of days returned. A quarter of days was still looping when the catalog freeze hit.

Maximum Product Subarray asks for the largest product of a contiguous slice. An array already gives a[i] for free. Nested i..j uses that and still pays O(n²). This is not Maximum Subarray: a negative prefix is poison for a sum, but a negative product is a loaded spring. The next negative can flip it into the answer.

This is an interview writeup, not a named-algorithm lecture. The Kadane post owns the sum recurrence. That pass does not transfer. Here we keep both the best and the worst product ending here, and we swap them when the new factor is negative.

The problem

Given a non-empty int[] nums, return the largest product of any contiguous subarray. The subarray must contain at least one element. Order of values is the layout you are given; you may not skip an index inside the chosen slice.

nums = [2, -3, -4]     →  24   the whole array; two negatives
nums = [5, 2, -1, 4]   →  10   slice [5, 2]; the -1 wrecks a longer run
nums = [-2, 0, -3]     →   0   zero beats either singleton
nums = [-5]            →  -5   the only legal slice

Note: A subsequence could drop the -1 between 2 and 4. This prompt forbids holes. Zero is a legal product, not a “skip this cell” token. Maximum Subarray is the same shape of question with addition; do not paste that reset onto a product.

Nested slices are the honest brute force

Every pair of endpoints is a candidate. Keep a running product from i so you do not re-multiply the inner range. Correct. Quadratic.

int maxProductNested(int[] nums) {
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        long prod = 1;
        for (int j = i; j < nums.length; j++) {
            prod *= nums[j];
            best = Math.max(best, (int) prod);
        }
    }
    return best;
}

At n = 20 this is a rounding error. At n in the tens of thousands you paid nested endpoints for a question two running endings answer in a single pass: largest and smallest product ending here?

One pass: max and min ending here, swap on a negative

Walk left to right. A slice that ends at this index is the singleton x, or some slice that already ended at i - 1 times x. You do not need every such slice. You need the extreme products among them — both of them — because you do not yet know the sign of x.

  • maxHere — largest product among slices that end at this index.
  • minHere — smallest (most negative, or a zero) product among those same endings.
  • best — the global max of maxHere.

If x is negative, swap maxHere and minHere first. The worst product is about to become the lead. Then extend: max(x, maxHere * x) and min(x, minHere * x). After the swap, assign maxHere first — minHere still holds the old max until the next line.

nums = [2, -3, -4]

i  x   swap?    max(x, max*x) / min(x, min*x)   maxHere  minHere  best
0   2  start                                     2        2        2
1  -3  yes       -3 / -6                        -3       -6        2
2  -4  yes       24 / -4                        24       -4       24

At i = 1 the swap is a no-op (both endings are 2), then the min becomes -6. At i = 2 the swap puts -6 in the lead; times -4 that is 24. Vanilla Kadane would have dropped the negative prefix and never kept -6 around. That is why the sum pass is the wrong tool.

The Java is that walk. Initialize both endings from nums[0] so a single negative is legal:

int maxProduct(int[] nums) {
    int maxHere = nums[0];
    int minHere = nums[0];
    int best = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int x = nums[i];
        if (x < 0) {
            int tmp = maxHere;
            maxHere = minHere;
            minHere = tmp;
        }
        maxHere = Math.max(x, maxHere * x);
        minHere = Math.min(x, minHere * x);
        best = Math.max(best, maxHere);
    }
    return best;
}

Time is O(n) — one pass, constant work per index. Space is O(1) besides the three running integers.

Note: Do not keep only maxHere. On [2, -3, -4] the best ending at -3 is -3; the answer later needs the worse ending -6. A zero sets both endings to 0 on its own, then the next value starts a new slice — that is the contiguous contract, not a hole.

What interviewers usually poke next

  • Return the bounds, not only the product. Track the candidate start of the current max-ending run, and commit when best improves. The three-int loop does not remember days.
  • All negative, no zero. Two negatives can win; a single leftover negative is the answer only when n = 1 or a zero splits the array into singletons. Initialize from nums[0].
  • Overflow. Products of int wrap. If the domain can exceed 32 bits, run maxHere / minHere / best as long and cast at the return if the prompt still wants int.
  • Empty input. The prompt promised a non-empty array. In production you would reject; at the board, ask.
  • Maximum sum. Maximum Subarray — reset a negative prefix. Do not mix the two recurrences.

You are done with this problem when you can say, out loud, why every slice is correct, why a negative ending must be kept (and swapped into the lead), and why Kadane on sums does not survive a sign flip.