medium
Maximum Subarray
Given an integer array containing at least one element, find the contiguous subarray with the largest sum and return that sum.
Constraints
- 1 ≤ n ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
Examples
in: nums = [-2,1,-3,4,-1,2,1,-5,4]
out: 6
[4,-1,2,1].
Recognition clues
- Contiguous subarray with maximum sum
- A negative running total can never help a later subarray
- Best ending here = max(element, best ending at previous + element)
Pattern
Kadane's AlgorithmThe best subarray ending at index i is either the element alone or the element appended to the best subarray ending at i - 1; a negative running sum is never worth carrying. This is a one-variable DP over "best ending here", which generalizes to product subarrays (track min and max) and stock problems.
Solution
Sweep the array keeping cur, the best sum of a subarray ending at the current position, and best, the overall maximum. At each element set cur = max(nums[i], cur + nums[i]) — if the previous run is negative, restart — then best = max(best, cur). This is Kadane's algorithm; a single pass with two variables suffices.
time O(n)space O(1)
Alternative approaches
- Prefix sums with a running minimum give the same result and generalize to circular arrays. Divide and conquer runs in O(n log n) and extends to segment-tree range queries.
Code it yourself
Solve in
Hints: