optimization • Intermediate

Kadane's Algorithm: Maximum Subarray Sum in Linear Time

Kadane's algorithm finds the contiguous subarray with maximum sum in O(N) time by making a greedy dynamic programming choice at each element: currMax = max(arr[i], currMax + arr[i]).

Intuitive Mental Model

The Gambling Streak: If your past cumulative profit is positive, you keep playing; if past losses exceed current earnings, you cut your losses, throw away past history, and start a fresh streak today.

C / TypeScript ImplementationHardware & Algorithmic Standard

function maxSubArray(nums: number[]): number {
  let maxSoFar = nums[0];
  let currMax = nums[0];

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

Key Architectural Takeaways

•Linear O(N) Time: Evaluates all contiguous subarray combinations in a single forward pass.
•O(1) Space: Maintains only two running scalar variables.

Common Coding Mistake

Initializing maxSoFar to 0 instead of nums[0], failing when all array numbers are negative.

Optimal Solution

Initialize both maxSoFar and currMax to nums[0].

Next: Dutch National Flag: In-Place 3-Way Partitioning