53. Maximum Subarray

RUN IT Extend or restart — keep the running max

TYPESCRIPT The solution, annotated

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

  for (let i = 1; i < nums.length; i++) {
    // Drop the prefix the moment it hurts: if curSum < 0, extending with it
    // only makes the new subarray smaller than starting fresh at nums[i].
    curSum = Math.max(nums[i], curSum + nums[i]);
    best = Math.max(best, curSum);
  }

  return best;
}

Reading it block by block

INTERVIEWFollow-ups they'll ask

• "Return the actual subarray, not just the sum." Add a windowStart that resets to i on restart, and save bestStart / bestEnd whenever best updates.
• "What if the array is circular?" (LC 918) The answer is either a normal subarray (run Kadane) or wraps around — equivalent to total - minSubarraySum. Take the max of both cases; watch the all-negative edge case.
• "Maximum product subarray?" (LC 152) Track both maxSoFar and minSoFar because a negative times a negative can become the new max.
• "What's the brute force?" O(n²) — try every (start, end) pair. Kadane exploits the fact that a subarray with a negative prefix can always be improved by dropping that prefix.
• "All-negative input?" The answer is the single largest (least negative) element. Seeding with nums[0] handles this; a curSum = 0 seed would silently return 0, which is wrong.

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

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

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

  return best;
}

FLASHCARDS Tap to flip