04. Maximum Subarray (Kadane's Algorithm)

Difficulty:MediumPattern:Dynamic Programming / KadaneTime:O(n)Space:O(1)

Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.

How It Works & Algorithmic Design

Solves using Kadane's Dynamic Programming Algorithm:

State Definition: At index $i$, decide whether to add nums[i] to the existing subarray or start a brand new subarray starting at nums[i].
Transition Formula: currentSum = Math.max(nums[i], currentSum + nums[i]).
Global Track: maxSum = Math.max(maxSum, currentSum).
Initialization: Set currentSum = nums[0] and maxSum = nums[0].

Why This Approach Works Best

Brute force checking all contiguous subarrays takes $O(n^2)$ time. Kadane's algorithm makes local optimal decisions at every step, reducing the runtime to optimal linear $O(n)$ time and $O(1)$ auxiliary space.

Example Walkthrough

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

Array containing negative and positive integers.

Kadane Trace: Subarray [4, -1, 2, 1] gives currentSum=6, which is the highest recorded.

Restarts subarray when current sum drops below current element.

Output: 6

Maximum contiguous subarray sum.

Answer: Kadane's Algorithm implementation

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;
}

💡 Iterative dynamic programming approach to find maximum contiguous subarray sum.

Key Takeaways

Decides whether to extend current subarray or start fresh at each index.
Works correctly even if all numbers in the array are negative.
Optimal linear runtime of $O(n)$ time and $O(1)$ space.