Maximum Subarray
Kadane's — running sum reset to current value whenever it goes negative; track running max.
2 min read
dp kadane array
Problem#
Return the largest sum of any contiguous non-empty subarray.
Examples#
[-2,1,-3,4,-1,2,1,-5,4]→6([4,-1,2,1]).[1]→1;[5,4,-1,7,8]→23.
Constraints#
1 <= nums.length <= 10^5.
Approach#
Kadane: at each index, cur = max(nums[i], cur + nums[i]). Track the running max.
Solution#
class Solution {public: int maxSubArray(vector<int>& nums) { int cur = nums[0], 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; }};func maxSubArray(nums []int) int { cur, best := nums[0], nums[0] for i := 1; i < len(nums); i++ { if nums[i] > cur+nums[i] { cur = nums[i] } else { cur = cur + nums[i] } if cur > best { best = cur } } return best}from typing import List
class Solution: def maxSubArray(self, nums: List[int]) -> int: cur = best = nums[0] for x in nums[1:]: cur = max(x, cur + x) best = max(best, cur) return bestfunction maxSubArray(nums) { let cur = nums[0], 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 maxSubArray(int[] nums) { int cur = nums[0], 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; }}function maxSubArray(nums: number[]): number { let cur = nums[0], 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;}Editorial#
The invariant: cur is the max subarray sum ending at index i. Resetting to nums[i] whenever extending hurts is the optimal choice — never carry a net-negative prefix forward. One pass, constant space.
Complexity#
- Time:
O(n). - Space:
O(1).
Concept revision#
Related#