Kadane's Maximum Subarray
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Profit and loss figures, temperature changes, score swings: sometimes you need the best stretch of consecutive values. A slow solution is easy to write. Kadane's idea gets the same answer in one pass.
The maximum subarray problem
Subarray means a run of neighbouring items of a list. [4, -1, 3] is a subarray of the profits above, but [4, 3] is not, because it skips an item.
A shop has daily profit and loss figures. Which run of consecutive days gives the largest total? Check every start and every end. This brute force is slow, but it is the right first answer.
profit = [3, -5, 4, -1, 3, -2]best = profit[0]for start in range(len(profit)): total = 0 for end in range(start, len(profit)): total += profit[end] best = max(best, total)print(best)Example 1 · Brute force with sum and slices
nums = [2, -3, 4, -1, 2]best = max(sum(nums[i:j]) for i in range(len(nums)) for j in range(i + 1, len(nums) + 1))print(best)5
What this code does
- Every slice
nums[i:j]is a subarray, andsumadds it up. - It is short but costs O(n cubed): O(n squared) slices, each summed in O(n).
- Use it to check a faster solution on small inputs.
Every start meets every end: O(n squared) time. Doubling the list makes the work four times larger.
Idea: the best sum ending here
Kadane's algorithm finds the maximum subarray sum in one pass. It keeps the best sum of a run ending at the current item and the best sum seen so far.
At each day ask one question: is it better to extend yesterday's run, or to start fresh today? If the run so far is negative, it only hurts, so drop it and begin again.
profit = [3, -5, 4, -1, 3, -2]current = best = profit[0]for value in profit[1:]: current = max(value, current + value) best = max(best, current)print(best)Example 2 · Watch Kadane work
profit = [3, -5, 4, -1, 3, -2]current = best = profit[0]print(profit[0], current, best)for value in profit[1:]: current = max(value, current + value) best = max(best, current) print(value, current, best)3 3 3 -5 -2 3 4 4 4 -1 3 4 3 6 6 -2 4 6
What this code does
- Each line shows the day's value, the best run ending there, and the best so far.
- At the value 4 the run restarts: 4 beats -2 + 4.
- The final best, 6, is the run 4, -1, 3.
Example 3 · Kadane as a function
def max_subarray(nums): current = best = nums[0] for value in nums[1:]: current = max(value, current + value) best = max(best, current) return best
print(max_subarray([1, 2, 3]))print(max_subarray([-4]))print(max_subarray([5, -9, 6]))6 -4 6
What this code does
- An all-positive list sums everything: 6.
- A single negative item is its own answer.
- In [5, -9, 6] the run 5, -9 is worse than starting fresh at 6.
current is the best run that ends at this day. best is the best current seen so far. One pass: O(n) time, O(1) space.
All-negative lists
If every number is a loss, the answer is the smallest loss, not 0. Start best from the first item, never from 0. A start of 0 quietly allows an empty run that the problem does not allow.
losses = [-8, -3, -6]current = best = losses[0]for value in losses[1:]: current = max(value, current + value) best = max(best, current)print(best)Example 4 · The mistake of starting at zero
losses = [-8, -3, -6]wrong = current = 0for value in losses: current = max(value, current + value) wrong = max(wrong, current)right = current = losses[0]for value in losses[1:]: current = max(value, current + value) right = max(right, current)print(wrong, right)0 -3
What this code does
- Starting at 0 never lets the answer go below 0, so an empty run wins.
- Starting from the first item gives the true answer, -3.
- Always check an all-negative input when you write Kadane.
The result is -3, the least bad single day.
Return the subarray itself
Interviewers often want the run, not just the sum. Remember where the current run began, and record the range whenever a new best appears.
profit = [3, -5, 4, -1, 3, -2]current = best = profit[0]start = best_start = best_end = 0for i in range(1, len(profit)): if profit[i] > current + profit[i]: current = profit[i] start = i else: current += profit[i] if current > best: best = current best_start, best_end = start, iprint(best, profit[best_start:best_end + 1])Example 5 · Best week of sales: a fixed window
sales = [4, 1, 7, 2, 9, 3]k = 3window = sum(sales[:k])best = windowfor i in range(k, len(sales)): window += sales[i] - sales[i - k] best = max(best, window)print(best)18
What this code does
- When the length k is fixed, slide a window: add the new item and drop the old one.
- That is a different problem from Kadane, where any length is allowed.
- O(n) time, O(1) space.
A new run starts only when the old run is negative. The slice at the end copies the best range.
Next step
Check your understanding
11 quick questions