Maximum Subarray

Intuition

You want the largest possible sum of a contiguous subarray.

As you scan left→right, any running sum that dips below zero is a liability—adding it to future elements can only make them smaller. So, the best prefix to carry forward is either:

• “keep extending” the current subarray, or
• “restart here” at the current element if the previous sum is harmful.

Approach

1. Maintain two values while iterating:

• curr: the best sum of a subarray that must end at the current index.
• best: the best sum seen anywhere so far.

1. For each x:

• curr = max(x, curr + x) (extend vs. restart)
• best = max(best, curr)

1. Return best. Edge cases

• All negatives: Kadane still works; best will be the maximum (least negative) single element.
• Length 1: return that element.
• If the problem variant allows empty subarray, define whether empty sum (0) is permissible; the classic problem does not.

Proof of Correctness

We prove by induction on the index i:

• Invariant: After processing i, curr equals the maximum sum of any subarray that ends at i, and best equals the maximum sum of any subarray in nums[0..i].
• Maintenance: For element x = nums[i], any optimal subarray ending at i is either:
  • the single element [x], or
  • the optimal subarray ending at i-1 extended by x (sum curr_old + x). Taking max(x, curr_old + x) preserves optimality for curr. Updating best = max(best, curr) preserves the global optimum.
• Initialization: At i = 0, curr = best = nums[0].

Thus, by induction, at the end best is the maximum subarray sum.

Complexity

• Time: O(n) single pass.
• Space: O(1) extra space.

Code

export function maxSubArray(nums: number[]): number {
  let curr = nums[0];
  let best = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const x = nums[i];
    curr = Math.max(x, curr + x);
    best = Math.max(best, curr);
  }
  return best;
}

def maxSubArray(self, nums):
    curr = nums[0]
    best = nums[0]

    for x in nums[1:]:
        curr = max(x, curr + x)
        best = max(best, curr)
    return best