maw.sh > Mahmoud Ashraf Website

SupportPalestine

53. Maximum Subarray 🔗

Date: Jun 08, 2024

Tags: kadane-algorithm

Description

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

Example 1:

      Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
      Output: 6
      Explanation: The subarray [4,-1,2,1] has the largest sum 6.
      

Example 2:

      Input: nums = [1]
      Output: 1
      Explanation: The subarray [1] has the largest sum 1.
      

Example 3:

      Input: nums = [5,4,-1,7,8]
      Output: 23
      Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
      

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Optimal

So, to solve the maximum subarray problem, we have to use Kadane’s algorithm by keep track of the latest max and current max until we get finish the array.

function maxSubArray(nums: number[]): number {
  let max = nums[0];
  let current = 0;

  for (const x of nums) {
    current = Math.max(x, current + x);
    max = Math.max(current, max);
  }

  return max;
}

export { maxSubArray };