Topic: Learning notes

LeetCode 152: Why maximum product subarray needs both extremes

My Maximum Product Subarray attempt, the counterexample that broke it, and the final O(n) maximum-and-minimum state solution with an invariant and brute-force checks.

This problem looks like Maximum Subarray with multiplication in place of addition. That change means keeping only the largest local result is no longer enough. A negative number reverses the order: the smallest negative product from the previous step can become the largest positive product after another negative number.

My first attempt tracked an absolute value and a separate sign flag. As the branches grew, the variables stopped having one stable meaning. After getting stuck, I used an AI hint to switch to the maximum and minimum products directly. The final code is short, but the useful part is understanding why those two states cover every candidate.

The problem

LeetCode 152: Maximum Product Subarray gives an integer array and asks for the largest product of a nonempty contiguous subarray.

For [2,3,-2,4], the answer is 6 from [2,3]. For [-2,0,-1], the answer is 0. Multiplying the nonadjacent values -2 and -1 is not allowed. The input contains 1 to 20000 integers, each between -10 and 10. Every subarray product and the final answer fit in a signed 32-bit integer.

My first attempt managed signs by hand

I renamed this version so it can appear beside the final function.

function maxProductFirstAttempt(nums: number[]): number {
    let endHere = nums[0];
    let endHereAbs = nums[0];
    let isEndHereNegative = nums[0] < 0;
    let best = nums[0];

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === 0) {
            endHere = 0;
            endHereAbs = 0;
            isEndHereNegative = false;
        } else if (isEndHereNegative) {
            if (nums[i] < 0) {
                endHere = Math.abs(endHereAbs * nums[i]);
                if (Math.abs(nums[i] * endHereAbs) > 0 - nums[i]) {
                    endHereAbs = nums[i] * endHereAbs;
                } else {
                    endHereAbs = nums[i];
                }
            } else {
                endHere = nums[i];
                if (Math.abs(nums[i] * endHereAbs) > nums[i]) {
                    endHereAbs = nums[i] * endHereAbs;
                } else {
                    endHereAbs = nums[i];
                }
            }
            isEndHereNegative = endHere < 0;
        } else {
            if (nums[i] > 0) {
                endHere = Math.max(endHere * nums[i], nums[i]);
                if (Math.abs(nums[i] * endHereAbs) > nums[i]) {
                    endHereAbs = nums[i] * endHereAbs;
                } else {
                    endHereAbs = nums[i];
                }
            } else {
                endHere = nums[i];
                if (Math.abs(nums[i] * endHereAbs) > 0 - nums[i]) {
                    endHereAbs = nums[i] * endHereAbs;
                } else {
                    endHereAbs = nums[i];
                }
            }
            isEndHereNegative = endHere < 0;
        }

        best = Math.max(endHere, best, endHereAbs);
    }

    return best;
}

This attempt recognized that negative values require another state. The problem is that endHereAbs sometimes stores a negative value, sometimes a product, and sometimes participates in an absolute-value comparison. isEndHereNegative is derived only from endHere. The three variables do not maintain a stable invariant, so the branches are difficult to verify.

[-1,-1,-2] is a counterexample. The correct result is 2 from [-1,-2], but this version returns 1. Changing one comparison operator may repair that path, but the state definitions would still be unclear.

My second attempt keeps the maximum and minimum

This is the version I completed after the hint:

function maxProduct(nums: number[]): number {
    let maxEndingHere = nums[0];
    let minEndingHere = nums[0];
    let best = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        const previousMax = maxEndingHere;
        const previousMin = minEndingHere;

        maxEndingHere = Math.max(previousMin * num, previousMax * num, num);
        minEndingHere = Math.min(previousMin * num, previousMax * num, num);
        best = Math.max(best, maxEndingHere);
    }

    return best;
}

There is no separate branch for a positive, negative, or zero value. Each iteration compares the same three candidates:

1. Start again with num.
2. Extend the previous maximum product with num.
3. Extend the previous minimum product with num.

For a positive num, the previous maximum usually produces the new maximum. For a negative num, the previous minimum may become the new maximum. Comparing all three candidates handles both cases without sign-specific branches.

The state invariant

After processing index i:

• maxEndingHere is the largest product among all nonempty contiguous subarrays ending exactly at i.
• minEndingHere is the smallest product among the same candidates.
• best is the largest product found anywhere from index 0 through i.

Every contiguous subarray ending at i is either [nums[i]] or a contiguous subarray ending at i - 1 multiplied by nums[i]. Once all previous candidates are multiplied by the same number, an extreme result can only come from the previous maximum or minimum. Values between those extremes cannot exceed both endpoints. Keeping previousMax and previousMin therefore covers every candidate.

Both previous values must be copied before either state is updated. Using the new maxEndingHere while calculating minEndingHere would mix states from two iterations and use the current element twice.

Tracing [2,-5,-2,-4,3]

At index 2, multiplying -2 by the previous minimum -10 produces the new maximum 20. At index 4, the local maximum 8 is extended by 3 to produce the answer 24.

Zero resets the state without a special branch. All extended candidates contain zero, and the standalone candidate is also zero. The next nonzero value can start a new subarray through the num candidate.

Brute force and its limit

The direct approach fixes every starting point and multiplies values while moving the endpoint right. There are O(n²) contiguous subarrays. This version is useful as a reference for small tests, but the input can contain 20000 elements.

function bruteForce(nums: number[]): number {
    let best = nums[0];

    for (let start = 0; start < nums.length; start++) {
        let product = 1;
        for (let end = start; end < nums.length; end++) {
            product *= nums[end];
            best = Math.max(best, product);
        }
    }

    return best;
}

The second attempt compresses all starting points into two extreme states. It visits each element once, so runtime is O(n) and extra space is O(1). The function returns one number and does not modify the input. This is asymptotically optimal because every input value can affect the answer and must be inspected.

Executable checks

import assert from "node:assert/strict";

assert.equal(maxProduct([-2, 0, -1]), 0);
assert.equal(maxProduct([-3, 0, 1, -2]), 1);
assert.equal(maxProduct([-1, -2, -9, -6]), 108);
assert.equal(maxProduct([2, -5, -2, -4, 3]), 24);
assert.equal(maxProduct([-1, -1, -2]), 2);
assert.equal(maxProduct([-3]), -3);
assert.equal(maxProduct([0]), 0);

let cases = 0;
for (let length = 1; length <= 7; length++) {
    for (let encoded = 0; encoded < 5 ** length; encoded++) {
        let value = encoded;
        const nums = Array.from({ length }, () => {
            const element = value % 5 - 2;
            value = Math.floor(value / 5);
            return element;
        });
        const before = [...nums];

        assert.equal(maxProduct(nums), bruteForce(nums));
        assert.deepStrictEqual(nums, before);
        cases++;
    }
}

assert.equal(cases, 97655);

The checks include my four examples, the first attempt’s counterexample, a single negative value, and a single zero. They also compare 97655 arrays of lengths 1 through 7, using values from -2 through 2, against the brute-force reference and verify that the input is unchanged. These tests passed. Finite tests support the implementation, while the invariant explains why it works for all valid inputs.

Common mistakes

• Keeping only the maximum product loses a negative value that could become the next maximum.
• Initializing best to zero incorrectly allows an empty subarray for inputs such as [-3].
• Calculating the minimum from an already updated maximum uses the current element twice.
• Adding separate zero branches is unnecessary. The standalone num candidate handles both zero and restarting.

What I learned

Maximum Subarray needs one local maximum because adding the same number preserves the order of candidates. Multiplication by a negative number reverses that order, so Maximum Product Subarray must keep both extremes.

The recurrence is easier to reconstruct when each variable has a precise meaning: which candidates it represents, where those candidates must end, and why no other information is needed. With that invariant in place, the original sign branches reduce to two state updates.

References

• LeetCode 152: Maximum Product Subarray: official statement, examples, and constraints.
• Node.js assert: executable assertions.