Maximum Product Subarray

• Maximum product subarray asks for the largest product of any contiguous non-empty subarray.
• A negative element can turn the smallest product into the largest, so track both max and min.
• At each position, consider three candidates: nums[i], prevMax * nums[i], prevMin * nums[i].
• A zero resets both products, and the next element restarts the subarray.
• Compute both new values from the previous values before overwriting.
• Time is O(N) and space is O(1).

What is the Maximum Product Subarray problem?

Given an array of integers that may include negative numbers and zeros, find the maximum product obtainable from any contiguous non-empty subarray. This is LeetCode 152.

For example, given [2, 3, -2, 4], the maximum product is 6 from the subarray [2, 3].

Why do we need both max and min products?

Unlike sums, products have a twist: multiplying by a negative number flips the sign. The largest product so far becomes the smallest, and the smallest becomes the largest. Keeping only a running maximum is not enough because the real champion might be hiding in a very negative running minimum that a later negative flips into a large positive.

// Example: [-2, 3, -4]
// After -2: max=-2, min=-2
// After 3:  max=3,  min=-6  (3 alone is better than -2*3=-6)
// After -4: max=24, min=-12 (min*(-4)=(-6)*(-4)=24!)
// The answer 24 came from the MIN track, not the MAX track

How does the algorithm work?

package com.bank.service;

public class MaxProductSubarrayService {

    /**
     * Finds the most profitable continuous multiplier chain.
     * Used by the National Bank of India wealth-management desk.
     */
    public static long maxProduct(int[] multipliers) {
        long prevMax = multipliers[0];
        long prevMin = multipliers[0];
        long globalMax = multipliers[0];

        for (int i = 1; i < multipliers.length; i++) {
            long val = multipliers[i];

            // Compute from previous values before overwriting
            long candMax = Math.max(val,
                Math.max(prevMax * val, prevMin * val));
            long candMin = Math.min(val,
                Math.min(prevMax * val, prevMin * val));

            prevMax = candMax;
            prevMin = candMin;
            globalMax = Math.max(globalMax, prevMax);
        }
        return globalMax;
    }

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

javac -d out com/bank/service/MaxProductSubarrayService.java
java -cp out com.bank.service.MaxProductSubarrayService

Max product: 48

How does the swap trick simplify the code?

A cleaner way to handle the negative flip is to swap the running maximum and minimum whenever the current element is negative, then update each normally.

for (int i = 1; i < nums.length; i++) {
    if (nums[i] < 0) {
        long temp = prevMax;
        prevMax = prevMin;
        prevMin = temp;
    }
    prevMax = Math.max(nums[i], prevMax * nums[i]);
    prevMin = Math.min(nums[i], prevMin * nums[i]);
    globalMax = Math.max(globalMax, prevMax);
}

How are zeros handled?

Multiplying by zero collapses both running products to zero. The next element simply restarts the subarray from itself, because Math.max(next, 0 * next) = Math.max(next, 0) = next (for positive next). Zeros are natural terminators that split the array into segments.

// Example: [2, 3, 0, 4, 5]
// After 0: max=0, min=0 (both reset)
// After 4: max=4, min=4 (restart)
// After 5: max=20, min=20

What are the edge cases?

Several edge cases require attention.

• Single negative element: the answer is that negative number.
• Two negatives: their product is positive and may be the answer.
• All zeros: the answer is 0.
• Odd count of negatives: the maximum product excludes one negative from either end.
• Overflow: products grow much faster than sums. Use long and test with large inputs.

package com.bank.core;

public class MaxProductEdgeCases {
    public static void main(String[] args) {
        System.out.println(maxProd(new int[]{-5}));         // -5
        System.out.println(maxProd(new int[]{-3, -4}));     // 12
        System.out.println(maxProd(new int[]{0, 0, 0}));    // 0
        System.out.println(maxProd(new int[]{-1, -2, -3})); // 6
    }

    static long maxProd(int[] arr) {
        long pMax = arr[0], pMin = arr[0], best = arr[0];
        for (int i = 1; i < arr.length; i++) {
            long a = pMax * arr[i], b = pMin * arr[i];
            pMax = Math.max(arr[i], Math.max(a, b));
            pMin = Math.min(arr[i], Math.min(a, b));
            best = Math.max(best, pMax);
        }
        return best;
    }
}

-5
12
0
6

What is the time and space complexity?

Time is O(N): a single pass with constant work per element. Space is O(1): three scalar variables. This is optimal.

How is this different from maximum subarray sum?

The key difference is that products require tracking both max and min, while sums only need the max.

| Aspect | Max Subarray Sum | Max Product Subarray |
|---|---|---|
| State variables | 1 (currentMax) | 2 (currentMax, currentMin) |
| Why? | Sums do not flip sign | Products flip on negatives |
| Zero handling | Natural (adds zero) | Resets products |
| Overflow risk | Moderate | High (products grow fast) |

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• Dual tracking is the one key idea: the entire difference from sum Kadane is carrying two running values instead of one.
• Snapshot before overwrite: computing both new max and min from the previous values before overwriting is the implementation pitfall.
• Test three cases: odd negatives, paired negatives, and embedded zeros are the three cases where naive solutions break.
• Prefix-suffix product approach: an alternative O(N) approach computes prefix products left to right and suffix products right to left, taking the maximum across both, which avoids tracking min entirely.