53. Maximum SubarrayMedium

Optimal Approach (Kadane's Algorithm)

Explanation

Kadane's Algorithm allows us to solve this in a single pass. We maintain a currentSum that resets to 0 if it ever drops below 0 (because a negative prefix will only decrease the sum of any future sequence). We continuously update maxSum with the highest currentSum seen so far.

Complexity

• Time Complexity: O(N) because we iterate through the array exactly once.
• Space Complexity: O(1) as we only store two numeric variables.

Implementation

function maxSubArrayOptimal(nums: number[]): number {
  let maxSum = -Infinity;
  let currentSum = 0;
  
  for (let i = 0; i < nums.length; i++) {
    currentSum += nums[i];
    
    if (currentSum > maxSum) {
      maxSum = currentSum;
    }
    
    if (currentSum < 0) {
      currentSum = 0;
    }
  }
  
  return maxSum;
}