Topic: Learning notes

LeetCode 53: Maximum subarray without rescanning every starting point

My O(n²) backward scan and final O(n) solution, with the distinction between endingHere and best, all-negative inputs, loop invariants, and executable tests.

I first fixed the current position and scanned backward, adding each possible segment to find the largest sum. That followed the problem directly, but repeated too much work on long arrays.

With AI hints and a code skeleton, I replaced the inner while loop with a result carried over from the previous iteration. This note preserves my initial version and the final version I completed. It also explains why one local best value is enough and why all-negative inputs matter.

The problem

LeetCode 53: Maximum Subarray asks for the largest sum of a nonempty contiguous subarray. Return the sum, not the indices. Elements must stay adjacent. Sorting or skipping negative elements would change the problem.

For [-2,1,-3,4,-1,2,1,-5,4], the answer is 6 from [4,-1,2,1]. The input contains 1 to 100000 integers between -10000 and 10000. This article covers the O(n) solution, not the divide-and-conquer follow-up.

My initial backward scan

I renamed the initial function so both versions can live in the same file.

function maxSubArrayOriginal(nums: number[]): number {
    let max = nums[0];
    let minIndex = 0;
    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        let maxSum = nums[i];
        let j = i;
        let minIdx = 0;
        while (j >= minIndex) {
            sum += nums[j];
            if (sum >= maxSum) {
                maxSum = sum;
                minIdx = j;
            }
            j--;
        }
        if (maxSum > max) {
            max = maxSum;
            minIndex = minIdx;
        }
    }
    return max;
}

The outer loop fixes the right endpoint i, and the inner loop adds elements going left. I tried to narrow future searches with minIndex, but that cannot guarantee enough work is skipped.

For an array containing only ones, each step left increases the sum. The selected minIdx returns to zero, and the next iteration scans all the way back again. The total work is 1 + 2 + ... + n, giving O(n²) worst-case time and O(1) extra space.

I do not rely on this moving boundary for the performance guarantee or treat minIndex as a general pruning rule. The repeated comparison of starting points is the work to remove.

My final solution keeps two different maxima

This is the final version I completed from the hints. It does not replace my solution with a different algorithm.

function maxSubArray(nums: number[]): number {
    let endingHere = nums[0];
    let best = nums[0];
    for (let i = 1; i < nums.length; i++) {
        endingHere = Math.max(endingHere + nums[i], nums[i]);
        best = Math.max(endingHere, best);
    }
    return best;
}

The two variables cover different sets of candidates:

• endingHere is the largest sum of a subarray that must end at the current position.
• best is the largest sum seen across every ending position processed so far.

endingHere can decrease because it must include the current element. It cannot stay at the previous position. best can keep an earlier result and does not have to end here.

Why there are only two choices

A nonempty contiguous subarray ending at i is either the current element alone or a subarray ending at i − 1 extended by the current element.

Every candidate in the second group adds the same nums[i]. A smaller previous sum cannot become larger than the previous maximum after adding the same number. Keeping only that maximum is sufficient.

The update is therefore:

endingHere = Math.max(previous endingHere + nums[i], nums[i])

A negative element does not automatically mean starting over. If the previous sum is 5 and the current number is -1, extending gives 4, which beats -1. If the previous sum is -3 and the current number is 4, starting over gives 4 instead of 1.

After updating the local result, compare it with the historical maximum:

best = Math.max(endingHere, best)

Following one example

For [-2,1,-3,4,-1,2,1,-5,4]:

The final endingHere is 5, but the answer is 6. Returning only the last local result would miss the best segment found earlier.

The invariant and initialization

After processing i, endingHere is the maximum sum among nonempty contiguous subarrays ending at i. Meanwhile, best is the maximum among all nonempty contiguous subarrays in the portion processed so far.

At i = 0, the only candidate is [nums[0]], so both variables start at nums[0]. The two choices described above produce the next correct local result. Updating best then includes that ending position. After the final iteration, every possible endpoint has been considered.

Initializing best to zero would be wrong for [-3,-1,-2]. The answer is -1 because an empty subarray is not allowed. The loop starts at 1 because the initial state already accounts for the first element.

Complexity and what is not stored

The final version scans the array once, using a fixed number of additions and comparisons per iteration. Runtime is O(n). Two numeric values and an index require O(1) extra space, and the output is one number. The input remains unchanged.

There is no array of local results and no record of the winning indices because the task asks only for the sum. Returning the segment itself would require tracking its starting point and the endpoints of the best segment.

Executable tests and a brute-force reference

Put the final function and this code in one TypeScript file, then run it in a TypeScript-capable environment. The reference does not use the initial version’s search boundary. It enumerates all contiguous segments and is suitable for checking small arrays.

import assert from "node:assert/strict";

assert.equal(maxSubArray([1]), 1);
assert.equal(maxSubArray([5, 4, -1, 7, 8]), 23);
assert.equal(maxSubArray([-1, 0]), 0);
assert.equal(maxSubArray([-3, -1, -2]), -1);
assert.equal(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6);
assert.equal(maxSubArray([0, 0]), 0);
assert.equal(maxSubArray(new Array(100000).fill(1)), 100000);

function bruteForce(nums: number[]): number {
    let best = nums[0];
    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        for (let j = i; j < nums.length; j++) {
            sum += nums[j];
            best = Math.max(best, sum);
        }
    }
    return best;
}

let cases = 0;
for (let n = 1; n <= 6; n++) {
    for (let encoded = 0; encoded < 5 ** n; encoded++) {
        let value = encoded;
        const nums = Array.from({ length: n }, () => {
            const element = value % 5 - 2;
            value = Math.floor(value / 5);
            return element;
        });
        const before = [...nums];
        assert.equal(maxSubArray(nums), bruteForce(nums));
        assert.deepStrictEqual(nums, before);
        cases++;
    }
}
assert.equal(cases, 19530);

These checks cover a single element, all-negative values, zeros, an optimum ending before the last position, and an input of 100000 elements. They also compare 19530 arrays of lengths 1 through 6, with values from -2 through 2, against the reference and verify that the input stays unchanged. The tests passed. Finite tests support the implementation but do not replace the correctness argument.

What I want to remember

My initial version searched again for the best sum ending at every position. The final version saves that result, so the next iteration only chooses whether to extend it or start over.

For similar problems, I want to separate the local state from the historical answer and explain why the other candidates can be discarded. That explains the improvement more precisely than simply removing a loop.

References

• LeetCode 53: Maximum Subarray: official problem and input constraints.
• Node.js assert: executable assertions.