#53 Maximum Subarray

Problem Statement

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

Intuition

At any position, we have two choices: extend the current subarray or start a new one from here. If the running sum becomes negative, it's better to start fresh.

This greedy insight is the basis of Kadane's algorithm.

Approach

1. Initialize currentSum and maxSum to the first element.
2. For each subsequent element, set currentSum = max(nums[i], currentSum + nums[i]).
3. Update maxSum = max(maxSum, currentSum).
4. Return maxSum.

Solution

function maxSubArray(nums: number[]): number {
  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;
}

Complexity Analysis