Problem
Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.
Example
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Subarray [4,-1,2,1] sums to 6.Solution
Kadane’s algorithm: at each index, decide whether to extend the current subarray or start fresh.
def max_sub_array(nums):
current = max_sum = nums[0]
for n in nums[1:]:
current = max(n, current + n)
max_sum = max(max_sum, current)
return max_sumfunction maxSubArray(nums) {
let current = nums[0], maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
maxSum = Math.max(maxSum, current);
}
return maxSum;
}int maxSubArray(vector<int>& nums) {
int current = nums[0], maxSum = nums[0];
for (int i = 1; i < nums.size(); i++) {
current = max(nums[i], current + nums[i]);
maxSum = max(maxSum, current);
}
return maxSum;
}public int maxSubArray(int[] nums) {
int current = nums[0], maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
maxSum = Math.max(maxSum, current);
}
return maxSum;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
If your running sum becomes negative, it can only hurt future sums. So we discard it and start fresh from the current element.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?