maximum-subarray.ts

/**
 * 53. Maximum Subarray  (Medium)
 * Link: https://leetcode.com/problems/maximum-subarray/
 *
 * Find the contiguous subarray with the largest sum and return that sum.
 *
 * Example:
 *   Input:  nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
 *   Output: 6            // [4, -1, 2, 1]
 *
 * Approach:
 *   Kadane's algorithm. Scan left to right keeping the best sum of a subarray
 *   ending at the current index: either extend the previous best or restart at
 *   the current element (whichever is larger). Track the global maximum.
 *
 * Time:  O(n)
 * Space: O(1)
 */
export function maxSubArray(nums: number[]): number {
  let current = nums[0];
  let best = nums[0];

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

  return best;
}