Python Algorithms

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.

  • Intermediate
  • 2 min read
  • 1 runnable example
What you'll learn
  • The best sum ending at each position
  • Starting fresh when the running sum hurts
  • O(n) time and O(1) memory
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
-2
1
-3
4
-1
2
1
-5
4
4 - 1 + 2 + 1 = 6 is the largest sum of any contiguous run.

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.

From a toll road to code
current = max(value, current + value)👛 Keep the purse, or start fresh if it is worse
best = max(best, current)🏆 Remember the fullest purse so far
current = best = values[0]🚩 Start with the first stretch
6💰 Best stretch: 4, -1, 2, 1
Extend the run while it helps; restart when it does not.
In one sentence

The 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

  1. current is the best sum of a run that ends at the current value.
  2. current = max(value, current + value) starts a new run when the old one would only lower the sum.
  3. best = max(best, current) keeps the best sum seen anywhere so far.
  4. 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

Run code →
main.py
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]))
Get a Run button for this example

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.

  1. Try empty, single-item, and duplicate-value inputs.
  2. Print state after every step to observe the algorithm.
  3. Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Run in the Python compiler →

Common mistakes

Starting from 0

With all-negative input the answer would wrongly be 0.

Problem
current = best = 0
Fix
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.

All challenges