Maximum Subarray Sum with Kadane's Algorithm in Python
Find the run of numbers with the largest sum in one pass, even when the list has negative values.
- The best sum ending at each position
- Starting fresh when the running sum hurts
- O(n) time and O(1) memory
Extend the run or start again
The problem
What was the best run of days for a stock, the longest winning streak in points, the most profitable stretch of a trip? These are all maximum-subarray questions. Checking every start and end is slow; Kadane's algorithm solves it in one pass.
Think of it like this
Kadane's algorithm is like walking along a path picking up gold and paying tolls. You keep a running purse for your current stretch. When your purse goes negative, carrying it only hurts, so you drop it and start fresh. You also remember the fullest purse you ever had.
current = max(value, current + value)👛 Keep the purse, or start fresh if it is worsebest = max(best, current)🏆 Remember the fullest purse so farcurrent = best = values[0]🚩 Start with the first stretch6💰 Best stretch: 4, -1, 2, 1The maximum subarray problem asks for the largest sum of consecutive items in a list; Kadane's algorithm solves it in O(n) time by tracking the best sum ending at each position.
Key points
currentis the best sum of a run that ends at the current value.current = max(value, current + value)starts a new run when the old one would only lower the sum.best = max(best, current)keeps the best sum seen anywhere so far.- Starting both from
values[0]makes lists of only negative numbers work.
When should you use it?
- Best period in time series: profits, scores, temperatures.
- Learning a classic one-pass dynamic programming idea.
- Interview questions about arrays.
When not to use it
- You need the start and end of the best run: track the indexes as well as the sums.
- The values are not in a meaningful order: then consecutive runs have no meaning.
Example code
def maximum_subarray_sum(values):
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
Result of running the code
6
Code explanation
At each value, the algorithm chooses between starting a new subarray and extending the previous one. It runs in O(n) time and O(1) space.
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Common mistakes
Starting from 0
With all-negative input the answer would wrongly be 0.
current = best = 0
current = best = values[0]
Finished this lesson?
Mark it as learned to track your progress.
Practice with a challenge
Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.
- Sliding Window Maximum Report the maximum of every window of k numbers. Hard
- Largest Adjacent-Digit Product Take every contiguous window of span digits and multiply its digits. Medium