Maximum Product Subarray: track max and min together

• Maximum Product Subarray – find the contiguous subarray whose product is the largest.
• Dual tracking – maintain both the running maximum and running minimum product ending at each index.
• Negative twist – multiplying by a negative turns a large positive into a large negative and vice versa, so the minimum can become the maximum.
• Three candidates – at each element x: x, x * prevMax, x * prevMin.
• Complexity – O(n) time, O(1) space.

What is the Maximum Product Subarray problem?

Given an integer array, find the contiguous subarray with the largest product and return that product. For example, in [2, 3, -2, 4], the maximum product is 6 from the subarray [2, 3].

At the National Bank of India, Pankaj multiplies consecutive daily growth factors to find the most profitable trading stretch.

Why is this harder than Maximum Sum Subarray?

In the sum version, a negative number just hurts. In the product version, a negative number flips the sign. A large negative product times another negative becomes a large positive product. So you cannot track just the maximum; you must also track the minimum.

// Sum: negative always hurts
// [-2, 3] sum = 1, max sum subarray is [3] = 3

// Product: two negatives help
// [-2, -3] product = 6, max product subarray is [-2, -3] = 6

How does the algorithm work?

At each element x, compute three candidates and pick the max and min:

package com.bank.analytics;

public class MaxProductSubarray {
    public static int maxProduct(int[] factors) {
        int currentMax = factors[0];
        int currentMin = factors[0];
        int globalMax = factors[0];

        for (int i = 1; i < factors.length; i++) {
            int x = factors[i];
            int candidate1 = x * currentMax;
            int candidate2 = x * currentMin;

            currentMax = Math.max(x, Math.max(candidate1, candidate2));
            currentMin = Math.min(x, Math.min(candidate1, candidate2));

            globalMax = Math.max(globalMax, currentMax);
        }
        return globalMax;
    }

    public static void main(String[] args) {
        int[] factors = {2, 3, -2, 4};
        System.out.println("Max product: " + maxProduct(factors));

        int[] factors2 = {-2, 0, -1};
        System.out.println("Max product: " + maxProduct(factors2));
    }
}

Max product: 6
Max product: 0

Why must you compute from OLD values before overwriting?

If you update currentMax first, then currentMin uses the new currentMax instead of the old one, producing wrong results.

// Wrong: currentMin uses the already-updated currentMax
currentMax = Math.max(x, Math.max(x * currentMax, x * currentMin));
currentMin = Math.min(x, Math.min(x * currentMax, x * currentMin));
// currentMax here is the NEW value, not the old one!

// Correct: save candidates from old values first
int cand1 = x * currentMax;
int cand2 = x * currentMin;
currentMax = Math.max(x, Math.max(cand1, cand2));
currentMin = Math.min(x, Math.min(cand1, cand2));

How does zero affect the result?

Zeros naturally reset both running products. When x is zero, x * currentMax and x * currentMin are both zero. The candidate x itself (zero) becomes the max if both products are negative. This effectively restarts the subarray after a zero, without special casing.

// Array: [2, 3, 0, -4, -5]
// At index 2 (value 0): currentMax = 0, currentMin = 0
// At index 3 (value -4): candidates are -4, 0, 0 -> max=-4, min=-4
// At index 4 (value -5): candidates are -5, 20, 20 -> max=20, min=-5
// globalMax = 20 (from subarray [-4, -5])

What is the time and space complexity?

| Approach | Time | Space |
|---|---|---|
| Dual-tracking DP | O(n) | O(1) |
| Brute force (all subarrays) | O(n^2) | O(1) |

What are common mistakes?

The most common mistake is tracking only the maximum and forgetting the minimum.

// Wrong: misses cases where two negatives multiply to a positive
currentMax = Math.max(x, x * currentMax);
globalMax = Math.max(globalMax, currentMax);
// For [-2, -3]: currentMax at index 1 = max(-3, -3*-2) = max(-3, 6) = 6
// This accidentally works here but fails for [-2, 0, -3]

// Correct: track both
int cand1 = x * currentMax;
int cand2 = x * currentMin;
currentMax = Math.max(x, Math.max(cand1, cand2));
currentMin = Math.min(x, Math.min(cand1, cand2));

What are the edge cases?

• Single element: return that element.
• All positive: the entire array is the maximum product subarray.
• One zero in the middle: the zero splits the array into two candidate subarrays.
• All negative, even count: the product of all is positive and may be the answer.
• All negative, odd count: exclude the smallest absolute value from one end.

int[] single = {-3};           // result: -3
int[] allPos = {1, 2, 3};      // result: 6
int[] withZero = {-2, 0, -3};  // result: 0
int[] evenNeg = {-2, -3};      // result: 6
int[] oddNeg = {-2, -3, -4};   // result: 12 (from [-3, -4])

How does this compare to Kadane's algorithm?

| Maximum Sum Subarray | Maximum Product Subarray |
|---|---|
| Track only current sum | Track both max and min product |
| Negative hurts, always | Negative flips max and min |
| Reset when sum < 0 | Reset handled naturally by zero |
| current = max(x, current+x) | max = max(x, x*max, x*min) |

What should a senior engineer know?

• The dual-tracking approach is a direct extension of Kadane's idea adapted for multiplication.
• For BigDecimal money amounts, use multiply and compareTo instead of * and >. Overflow is a concern with large integer products.
• In production, consider long or BigInteger if the array can contain large values.
• A variant asks for the minimum product subarray, which is solved by returning the global minimum instead.

What are common interview follow-up questions?

• How would you handle overflow? (Use long or detect overflow before multiplying.)
• What if the array contains only positive numbers? (Simple Kadane-style max tracking suffices.)
• Can you find the actual subarray, not just the product? (Track start/end indices alongside max/min.)