53. Maximum Subarray 🔗
Date: Jun 08, 2024
Tags: kadanealgorithm
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 <= 10^{5}

10^{4} <= nums[i] <= 10^{4}
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 };