Maximum Subarray Algorithm

Given an array of integers, find the contiguous subarray with the largest sum.

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 (the subarray [4, -1, 2, 1])

The intuition

At each position, you face a simple decision: should the current element join the existing subarray, or start a new one?

If the running sum so far is negative, it's dragging you down. Drop it. Start fresh from the current element.

This is Kadane's Algorithm. One pass. One decision at each step.

The code

function maxSubArray(nums) {
    let currentSum = nums[0];
    let maxSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

How it works

Walk through the array. At each element, currentSum is either the element itself (starting fresh) or the element added to the running sum (extending the subarray). Track the best maxSum you've seen.

Other approaches

Brute force: Check every possible subarray. O(n^3) time. Terrible.

Divide and conquer: Split the array in half, solve each half, handle the crossing subarray. O(n log n) time. Better, but still not optimal.

Complexity

• Time: O(n) — single pass.
• Space: O(1) — two variables.

Trade-offs

Kadane's is elegant and optimal for the basic problem. But if you need the actual subarray indices (not just the sum), you'll need to track start and end positions, which adds a bit of bookkeeping. If the problem asks for maximum product instead of sum, the approach needs modification since negative times negative is positive.