Kadane's Algorithm
The Intuition
Imagine you're walking down a street collecting coins off the ground. Some are gold (positive), some are cursed and cost you money (negative). At every single step, you face one simple question: is it worth carrying my current collection forward, or should I dump everything and start fresh from this spot?
The math makes the decision obvious. If your running total just went negative, every future coin you pick up would be worth more without that baggage. Drop it. Start over. But if your running total is still positive, it's helping you, so keep going. At every step, you just compare: current element alone versus current element plus whatever you've accumulated.
While you walk, you keep a mental note of the best collection you've ever held. Maybe it was three steps ago. Maybe it's right now. Doesn't matter. You just update that "personal best" whenever your current collection beats it.
That's the entire algorithm. One pass through the array. Two variables: your current running sum and your all-time best. The decision at each element is max(element, element + running_sum). The answer at the end is your all-time best. No nested loops, no prefix arrays, no dynamic programming table. Just a walk down the street, picking up coins, knowing when to cut your losses.
Maximum subarray sum, maximum circular subarray, maximum product subarray (with modification), or any problem asking for an optimal contiguous segment.
- Non-contiguous subsets (use DP/backtracking)
- Need the actual subarray indices alongside sum (need extra tracking)
- 2D subarray problems (use 2D prefix sum + Kadane)
Variations:
- Standard Kadane's: Maximum sum subarray in a linear array.
- With index tracking: Also return the start and end indices of the optimal subarray.
- Circular variant: Maximum subarray in a circular array using total - min_subarray trick.
- Maximum product: Track both max and min products (negative * negative = positive).
- all negatives
- single element
- all zeros
Key Points
- •Track current subarray sum and global maximum
- •Reset current sum to 0 (or current element) when it goes negative
- •Works in a single pass. No need for prefix sums.
- •Can be extended to track the subarray boundaries (start/end indices)
- •Handles all-negative arrays by initializing max to first element
Code Template
1 def max_subarray(nums):
2 """Maximum subarray sum (Kadane's algorithm)."""
3 max_sum = curr_sum = nums[0]
4 for num in nums[1:]:
5 curr_sum = max(num, curr_sum + num)
6 max_sum = max(max_sum, curr_sum)
7 return max_sum
8
9 def max_subarray_with_indices(nums):
10 """Return (max_sum, start, end) of the maximum subarray."""
11 max_sum = curr_sum = nums[0]
12 start = end = temp_start = 0
13
14 for i in range(1, len(nums)):
15 if nums[i] > curr_sum + nums[i]:
16 curr_sum = nums[i]
17 temp_start = i
18 else:
19 curr_sum += nums[i]
20
21 if curr_sum > max_sum:
22 max_sum = curr_sum
23 start, end = temp_start, i
24
25 return max_sum, start, end
26
27 def max_circular_subarray(nums):
28 """Maximum subarray sum in a circular array."""
29 total = sum(nums)
30 max_kadane = max_subarray(nums)
31
32 # Min subarray to find max circular = total - min_subarray
33 min_sum = curr_min = nums[0]
34 for num in nums[1:]:
35 curr_min = min(num, curr_min + num)
36 min_sum = min(min_sum, curr_min)
37
38 # If all elements are negative, max_kadane is the answer
39 if min_sum == total:
40 return max_kadane
41 return max(max_kadane, total - min_sum)Common Mistakes
- Initializing max_sum to 0 instead of arr[0] (fails on all-negative arrays)
- Forgetting to handle the empty array edge case
- Not resetting current_sum correctly. Should compare element vs current_sum + element