Maximum Product Subarray: Track Running Max AND Min

• Maximum Product Subarray – finds the contiguous slice of an array whose element product is largest, requiring dual state because multiplication can flip signs.
• Running max and min – maxProduct tracks the best product ending here; minProduct tracks the worst (most negative), which can become the best after a negative multiplier.
• Swap on negative – when the current element is negative, maxProduct and minProduct are swapped before the update so the sign flip routes values correctly.
• O(n) time, O(1) space – a single pass with three scalar variables: maxProduct, minProduct, and globalBest.
• Zero handling – a zero resets both running products naturally because max(0, 0 * anything) = 0.

What is the Maximum Product Subarray problem?

The Maximum Product Subarray problem asks for the contiguous subarray whose elements, when multiplied together, produce the largest product. Unlike the sum version, multiplication introduces a complication: a negative number can flip a very small (most negative) product into the largest product. This means tracking only the running maximum is not enough.

At the National Bank of India, Pankaj asks Rajesh to find the consecutive stretch of daily portfolio growth factors that produces the strongest compound effect, including reversal days where the factor is negative.

Why do you need both a running max and a running min?

In the additive Maximum Subarray (Kadane's), adding a negative value always reduces the sum, so you only need a running maximum. In the product version, multiplying a large negative running product by another negative element produces a large positive result. If you only tracked the running max, you would lose the large negative candidate, and when the next negative arrives you would miss the sign flip that creates the true maximum.

Example:  [2, 3, -2, 4, -1]

  Index:     0    1    2    3     4
  maxP:      2    6   -2    4    -4    (tracking only max: misses flip)
  minP:      2    3  -12  -48    48    (the min at index 2 becomes huge after two negatives)
  gBest:     2    6    6    6    48    (correct answer: 48 from entire array product)

How does the algorithm work internally?

You keep three values: maxProduct (best product ending here), minProduct (worst product ending here), and globalBest (best seen anywhere). All start at the first element.

• For each remaining element:
• If the element is negative, swap maxProduct and minProduct before updating.
• Set maxProduct = max(element, maxProduct * element).
• Set minProduct = min(element, minProduct * element).
• Set globalBest = max(globalBest, maxProduct).

The swap routes values correctly: a negative times the old max gives a small number, while the same negative times the old min (which may be negative) gives a large positive.

How do you implement it? (with code)

package com.bank.analysis;

import java.math.BigDecimal;

public class MaxProductSubarray {

    public static BigDecimal maxProduct(BigDecimal[] factors) {
        if (factors == null || factors.length == 0) {
            throw new IllegalArgumentException("Array must not be empty");
        }
        BigDecimal maxP = factors[0];
        BigDecimal minP = factors[0];
        BigDecimal globalBest = factors[0];

        for (int i = 1; i < factors.length; i++) {
            // Swap on negative: roles of max and min flip
            if (factors[i].signum() < 0) {
                BigDecimal temp = maxP;
                maxP = minP;
                minP = temp;
            }
            // Extend or restart
            maxP = factors[i].max(maxP.multiply(factors[i]));
            minP = factors[i].min(minP.multiply(factors[i]));
            // Update global best
            globalBest = globalBest.max(maxP);
        }
        return globalBest;
    }

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

Max product: 48

How is this different from Kadane's Algorithm (Maximum Sum)?

| Aspect | Maximum Sum (Kadane's) | Maximum Product |
|---|---|---|
| Operation | Addition | Multiplication |
| State needed | One running value (currentBest) | Two running values (maxP, minP) |
| Sign flip concern | No | Yes: negative times negative becomes positive |
| Swap step | Not needed | Swap maxP and minP when element is negative |
| Zero handling | No special case | Zero resets both products to zero naturally |
| Initialization | Both values to a[0] | All three values to a[0] |

// Kadane's (sum): one running value
BigDecimal cur = a[0], best = a[0];
for (int i = 1; i < n; i++) {
    cur = a[i].max(cur.add(a[i]));
    best = best.max(cur);
}

// Product: two running values + swap
BigDecimal maxP = a[0], minP = a[0], best = a[0];
for (int i = 1; i < n; i++) {
    if (a[i].signum() < 0) { var t = maxP; maxP = minP; minP = t; }
    maxP = a[i].max(maxP.multiply(a[i]));
    minP = a[i].min(minP.multiply(a[i]));
    best = best.max(maxP);
}

What happens with zeros in the array?

A zero resets both running products because any product through a zero is zero. Taking the maximum of the element alone (which is zero) and the element times a previous product (which is also zero) naturally restarts the run at the next element. No special code is needed.

// Array: [2, 3, 0, -2, 4]
// At index 2 (zero): maxP = max(0, 0) = 0, minP = min(0, 0) = 0
// The run restarts at index 3

What are the edge cases?

• Single element – return that element.
• All negative – if the count is even, the entire array product is positive and may be the answer; if odd, exclude one end element.
• Contains zeros – zeros split the array into segments; the answer is the best segment product or zero.
• All zeros – the answer is zero.
• Empty array – reject with an exception.

// All negative, even count: [-2, -3] → product = 6
// All negative, odd count: [-2, -3, -4] → best is [-2, -3] = 6 or [-3, -4] = 12

What about precision for financial data?

If the values are growth factors for a portfolio, you must use BigDecimal with multiply, max, and min via compareTo. Floating-point drift compounds dangerously over a long multiplied chain, and in banking this is unacceptable.

What are common interview follow-up questions?

• Why not just track the max product? – Because a negative times the most-negative product creates the largest positive.
• Can you return the actual subarray? – Yes, track start indices similar to Kadane's with index tracking.
• What if the array has only one negative? – The answer excludes the segment containing that negative, unless the rest is all zeros.
• Time and space? – O(n) time, O(1) space.