Tracking Min and Max Together: Why the Product Subarray Problem Breaks Kadane's

The moment a negative number appears in the input, the standard Kadane's algorithm — the one that solved Maximum Subarray in O(n) — breaks down. A negative times a negative is positive, which means the worst running product at position i might become the best running product at position i+1. Kadane's tracks one value per position. This problem needs two.

That's the entire insight. Everything else follows from it.

What the constraints force

1 <= nums.length <= 2 × 10^4 and -10 <= nums[i] <= 10. The length cap rules out O(n²) at any serious scale — twenty thousand elements means four hundred million iterations in the brute force, which is borderline on most judges and clearly not the intended path. The element range is small: values between -10 and 10, and the problem guarantees the answer fits in a 32-bit integer, so there's no overflow hazard in the product itself.

The constraint I care about most is the negative range. An element of -10 can turn a running product of -100 into +1000. This is the core tension: you cannot discard a negative running product the way Kadane's discards a negative running sum, because that negative product might be exactly what the next negative element needs. The algorithm has to stay aware of both extremes.

Brute force: try every subarray

Before anything clever, the direct approach: for every starting index i, extend rightward and track the running product. Check all n(n+1)/2 subarrays.

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        n = len(nums)
        result = nums[0]
        for i in range(n):
            product = 1
            for j in range(i, n):
                product *= nums[j]
                result = max(result, product)
        return result

public class Solution {
    public int MaxProduct(int[] nums) {
        int n = nums.Length;
        int result = nums[0];
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = i; j < n; j++) {
                product *= nums[j];
                result = Math.Max(result, product);
            }
        }
        return result;
    }
}

O(n²) time, O(1) space. It works and it handles all the edge cases correctly — the outer loop ensures single-element subarrays are considered, which covers the all-negatives case where the answer is the largest single element. The problem is purely speed: at n = 20,000 this is 200 million multiplications. Fine for tiny inputs, wrong for production.

The two-lookback DP

The key observation: at each position i, the maximum product of any subarray ending at i is one of three things — nums[i] alone, max_so_far * nums[i], or min_so_far * nums[i]. That third option is why this is different from Maximum Subarray. When nums[i] is negative, multiplying it by the most-negative running product gives you the most-positive result.

So we track two running values: max_prod (the best product ending at the current index) and min_prod (the worst product ending at the current index). At each step:

new_max = max(nums[i], max_prod * nums[i], min_prod * nums[i])
new_min = min(nums[i], max_prod * nums[i], min_prod * nums[i])

The global answer is the running maximum of all max_prod values.

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        max_prod = nums[0]
        min_prod = nums[0]
        result = nums[0]
 
        for i in range(1, len(nums)):
            candidates = (nums[i], max_prod * nums[i], min_prod * nums[i])
            max_prod = max(candidates)
            min_prod = min(candidates)
            result = max(result, max_prod)
 
        return result

public class Solution {
    public int MaxProduct(int[] nums) {
        int maxProd = nums[0];
        int minProd = nums[0];
        int result = nums[0];
 
        for (int i = 1; i < nums.Length; i++) {
            int a = nums[i];
            int b = maxProd * nums[i];
            int c = minProd * nums[i];
            maxProd = Math.Max(a, Math.Max(b, c));
            minProd = Math.Min(a, Math.Min(b, c));
            result = Math.Max(result, maxProd);
        }
 
        return result;
    }
}

O(n) time, O(1) space. Three comparisons per element, constant memory regardless of input size. This is what I'd ship.

Some implementations do the swap trick — if nums[i] < 0, swap max_prod and min_prod before multiplying. That works and is slightly more explicit about the sign-flip logic, but taking max and min of all three candidates handles it without the branch. I prefer the three-candidate form because it reads as a single idea rather than a conditional transformation.

Walking through [2, 3, -2, 4]

The example in the problem statement. Let's go step by step.

At i=0: initialize everything to 2. Result is 2.

At i=1, nums[1] = 3. Candidates: 3, 2×3=6, 2×3=6. max_prod = 6, min_prod = 3. Result becomes 6.

At i=2, nums[2] = -2. Candidates: -2, 6×(-2)=-12, 3×(-2)=-6. max_prod = -2, min_prod = -12. This is the interesting step — the running maximum dropped negative because the only subarray ending here that includes earlier elements produces a negative product. Result stays 6.

At i=3, nums[3] = 4. Candidates: 4, (-2)×4=-8, (-12)×4=-48. max_prod = 4, min_prod = -48. Result stays 6.

The answer is 6, from the subarray [2, 3]. Notice that min_prod at i=3 is -48 — if the array continued with a -1, the next step would produce max_prod = 48, which beats 6.

Edge cases and why they're handled

Single element. Initialized to nums[0], the loop never runs. Returns the only element. Correct — a single element is a valid subarray.

All negatives, e.g. [-3, -2, -1]. At i=0, both trackers start at -3. At i=1: candidates are -2, (-3)×(-2)=6, (-3)×(-2)=6. max_prod = 6, min_prod = -2. Result is 6. Correct — [-3, -2] produces the max product.

Zero in the array, e.g. [2, -3, 0, 4]. When nums[i] = 0, all three candidates include 0 × anything = 0 or just 0. Both trackers reset toward 0, which represents starting a fresh subarray after the zero. The element 4 can then form its own subarray and produce max_prod = 4. This is exactly why we include nums[i] alone as a candidate — it lets the algorithm restart.

[-2, 0, -1] from the problem. Result should be 0, not 2. At i=1, zero resets both trackers to 0. At i=2, candidates are -1, 0×(-1)=0, 0×(-1)=0. max_prod = 0. Result stays 0. The two elements [-2, -1] are not contiguous — they're separated by 0 — so the algorithm correctly never multiplies them.

Single positive, single negative. Both handled by initialization: the single element is both the max and min, and it becomes the result.

Complexity comparison

Both approaches use O(1) space, which is a nice property of this problem. The DP table is conceptually there (one entry per index, two values each), but you never need to store it — only the current step's values matter.

The mental model and where it appears

The pattern here is two-lookback DP with sign-awareness. You maintain two running values instead of one because the operation (multiplication) is not monotone with respect to positive/negative inputs. Addition is: a negative summand always makes the sum smaller, so Kadane's discards it by resetting to the current element. Multiplication is not: a negative multiplicand might make the product larger if the running product was itself negative.

Anytime you see "maximum/minimum over a contiguous subarray" combined with an operation that can flip sign or direction, think about whether you need a parallel minimum tracker alongside the maximum.

The sibling problems worth working after this one:

• LeetCode 53, Maximum Subarray — the addition version, where one tracker suffices. Worth solving first to understand why the product version needs more.
• LeetCode 238, Product of Array Except Self — no division, prefix/suffix products, different flavor but shares the "think about products differently" constraint.
• LeetCode 628, Maximum Product of Three Numbers — small fixed window instead of variable subarray; you can sort or just track the top two negatives and top three positives.
• LeetCode 1567, Maximum Length of Subarray With Positive Product — same sign-tracking intuition, different objective: length instead of value.

The jump from Maximum Subarray (53) to this problem (152) is exactly the jump from single-state Kadane's to dual-state Kadane's. House Robber (198) is a related series entry — it also uses two-lookback state, but the DP transition there is driven by index parity rather than sign. Recognizing the shared shape across these problems is what makes the mental model transferable.