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 };
