The problem
Given an integer array nums, return the largest sum of any subarray — a run of one or more consecutive elements.
Examples
01
- Input
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
- Output
6
02
- Input
nums = [1]
- Output
1
03
- Input
nums = [5, 4, -1, 7, 8]
- Output
23
Constraints
- 1 ≤ nums.length ≤ 10⁵
- −10⁴ ≤ nums[i] ≤ 10⁴
The idea
Kadane’s algorithm walks the array keeping here, the best sum of a run that ends at the current element. That run either extends the best run ending one step earlier, or starts fresh at this element — whichever is larger.
The greedy insight: if the run so far has gone negative, it can only make whatever follows smaller, so drop it. The answer is the largest here seen. For [−2, 1, −3, 4, −1, 2, 1, −5, 4]: here climbs 4, 3, 5, 6 across [4, −1, 2, 1] — 6.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def maxSubArray(self, nums: List[int]) -> int: # Kadane: the best run ending here either extends the one ending just before, # or starts afresh — whichever is larger. A negative run so far only drags it down. here = best = nums[0] for x in nums[1:]: here = max(x, here + x) best = max(best, here) return best