Maximum Subarray Sum (Kadane's)
Problem
Given an array of integers (positive, negative, or zero), find the largest possible sum of any contiguous subarray containing at least one element.
Input
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]Output
6The contiguous subarray [4, -1, 2, 1] has the largest sum.
def max_subarray_sum(nums):
cur = best = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return bestfunction maxSubarraySum(nums) {
let cur = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}class Solution {
public int maxSubarraySum(int[] nums) {
int cur = nums[0];
int best = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}
}int maxSubarraySum(vector<int>& nums) {
int cur = nums[0];
int best = nums[0];
for (int i = 1; i < (int)nums.size(); i++) {
cur = max(nums[i], cur + nums[i]);
best = max(best, cur);
}
return best;
}