Kadane's Algorithm: Maximum Subarray Sum
You'll learn how to find the largest possible sum of consecutive elements in an array using a clever single-pass technique.
The Problem
Imagine you have an array of numbers (both positive and negative), and you need to find which continuous slice of elements adds up to the biggest sum. For example, in [-2, 1, -3, 4, -1, 2, 1, -5, 4], the best subarray is [4, -1, 2, 1] with sum 6.
A brute-force approach checking every possible subarray would be slow. Kadane's Algorithm solves this in O(n) time using just O(1) extra space.
The Core Idea
Think of walking through the array, carrying a running sum. At each step, you make a choice: either add the current element to your existing sum, or start fresh from this element. Why start fresh? Because if your running sum has become negative, it's dragging you down—better to abandon it.
Meanwhile, track the best (maximum) sum you've seen so far.
How It Works
def max_subarray_sum(arr):
max_sum = arr[0]
current_sum = arr[0]
for i in range(1, len(arr)):
# Either extend current subarray or start new
current_sum = max(arr[i], current_sum + arr[i])
# Update best result seen so far
max_sum = max(max_sum, current_sum)
return max_sum
At each element, current_sum represents the best subarray ending at this position. We either continue the previous subarray or start anew.
The Analogy
It's like climbing hills: if you're in a valley (negative sum), sometimes it's better to restart your climb from the next position rather than dragging that deficit forward.
Key Takeaway: Kadane's Algorithm finds the maximum subarray sum in one pass by maintaining the best sum ending at each position, deciding at each step whether to extend or restart, achieving O(n) time with O(1) space.