Kadane's Algorithm
Kadane's algorithm finds the maximum sum contiguous subarray in O(n) time. It's elegant, it's fast, and once you understand the intuition, you'll never forget it.
The Core Idea
At each position, decide: should I extend the previous subarray, or start fresh from here? If the previous sum is negative, it's only dragging us down - start over. Otherwise, keep extending.
A negative prefix sum never helps. If everything before the current element sums to negative, drop it all and start fresh. The maximum subarray either includes the previous maximum or starts anew.
The Algorithm
def maxSubArray(nums):
max_sum = nums[0]
current_sum = nums[0]
for i in range(1, len(nums)):
# Extend or start fresh?
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
return max_sumVariation: Return the Subarray
def maxSubArrayWithIndices(nums):
max_sum = current_sum = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > current_sum + nums[i]:
current_sum = nums[i]
temp_start = i # Start fresh here
else:
current_sum += nums[i]
if current_sum > max_sum:
max_sum = current_sum
start = temp_start
end = i
return max_sum, nums[start:end + 1]Variations and Extensions
- Maximum subarray - Classic Kadane
- Maximum circular subarray - Also consider total - min subarray
- Maximum product subarray - Track both max and min (negatives flip)
- K maximum sums - Use heap with Kadane
Kadane's is actually DP in disguise. dp[i] = max sum ending at i = max(nums[i], dp[i-1] + nums[i]). We just don't need the whole array - only the previous value.