Kadane's algorithm
Why it exists
Problem: Finding the maximum subarray sum in a naive way takes O(n^2) by checking all possible windows.
Naive approach: Check all pairs of (start, end) indices and compute their sum.
Better idea: Keep a running total of the current subarray sum. If adding the current element makes the running total smaller than the element itself, it's better to just start a new subarray from the current element. This reduces the problem to a single O(n) pass.
Mental model
At each step, you decide whether to extend the current contiguous subarray or start a new one.
Walk through the array keeping track of the best sum ending at the current position. At each new number, you have a choice: either add it to the existing running subarray, or abandon the existing subarray and start fresh with just the new number. You start fresh if the new number alone is larger than the existing subarray plus the new number.
Repeated decision: extend the current subarray with this element, or restart the subarray from it? -> `current = max(nums[i], current + nums[i])`.
Explanation
Kadane's algorithm solves the maximum contiguous subarray sum problem in O(n) time and O(1) space. It is fundamentally a dynamic programming approach where the state is optimized to a single variable.
Two running values are maintained: `current` (the best subarray sum ending at the exact current position) and `best` (the overall best subarray sum seen anywhere so far). It is crucial to keep these distinct -- conflating them is the classic bug.
At each index `i`, we make a single choice: do we extend the previous subarray by adding `nums[i]`, or do we restart a new subarray beginning at `nums[i]`? We restart if `nums[i]` alone is strictly greater than `current + nums[i]`.
Let's hand-trace on `[-2, 1, -3, 4, -1, 2, 1, -5, 4]`:
i=0: current=-2, best=-2 (start)
i=1: -2+1=-1 < 1 -> restart. current=1, best=1
i=2: 1+(-3)=-2 >= -3 -> extend. current=-2, best=1
i=3: -2+4=2 < 4 -> restart. current=4, best=4
i=4: 4+(-1)=3 >= -1 -> extend. current=3, best=4
i=5: 3+2=5 >= 2 -> extend. current=5, best=5
i=6: 5+1=6 >= 1 -> extend. current=6, best=6
i=7: 6+(-5)=1 >= -5 -> extend. current=1, best=6
i=8: 1+4=5 >= 4 -> extend. current=5, best=6
Answer: 6 (subarray [4, -1, 2, 1] at indices 3..6)
The DP connection: this is a 1D dynamic-programming solution with the table collapsed to a single variable. The DP state would be "best subarray sum ending at index i", and since that state only ever reads the value at `i-1`, the whole array collapses to one rolling number -- the same space optimization covered in Space optimization and State and transition.
Common mistakes
- Failing on an all-negative array: The all-negative case is the trap: initialize `best` to `nums[0]`, not `0`, or an all-negative array wrongly returns `0`.
- Conflating current and best: Mixing up the sum ending *here* versus the global maximum sum. You must maintain both separately.
Recall questions
- What is the repeated decision made at each step in Kadane's algorithm?
- How is Kadane's algorithm related to dynamic programming?
- What happens if you initialize the maximum sum to 0 instead of the first element?
Questions & answers
Find the maximum contiguous subarray sum in an array of integers.
Use Kadane's algorithm. Maintain a running sum and a global max. At each step, update the running sum to max(num, running sum + num), then update global max.
Approach: This is the direct application of Kadane's algorithm.
Find the maximum contiguous subarray product.
Similar to Kadane's, but maintain both a running maximum and running minimum (since two negative numbers multiplied yield a positive).
Approach: Adapt the Kadane's pattern to track both extremes due to signs flipping on multiplication.
Continue learning
Previous: Prefix Sums
Previous: Two pointers
Related: Space optimization
Related: State & transition