Kadane's Algorithm (Maximum Subarray)
DSA · Classic Algorithms
Theory
Kadane's algorithm finds the contiguous subarray with the largest sum in a single pass. As it scans the array it keeps two values: the best sum of a subarray ending at the current position, and the best sum seen anywhere so far. At each element it decides whether to extend the previous subarray or start fresh from the current element: current = max(x, current + x). If the running sum becomes negative, carrying it forward can only hurt, so starting again is better. The overall answer is the maximum current value seen. This runs in O(n) time and O(1) space, compared with O(n^2) for checking every subarray. Tracking where each restart happens also gives the start and end indexes of the best subarray.
Why we use it
Maximum subarray appears directly in interviews and in practice for finding the best period of profit, the strongest signal segment, or the most active window in a time series.
When to use it
Use it whenever you need the maximum (or, with a sign change, minimum) sum of a contiguous range. For non-contiguous selections, other techniques apply.
How it works
- current = best = arr[0]
- For each next x
- x > current + x? Yes: Start new subarray at x. No: Extend: current += x.
- best = max(best, current)
- Return best
Syntax
current = best = a[0]
for x in a[1:]:
current = max(x, current + x)
best = max(best, current)
Time O(n) Space O(1)Example
def max_subarray(nums):
current = best = nums[0]
start = best_start = best_end = 0
for i in range(1, len(nums)):
if nums[i] > current + nums[i]:
current, start = nums[i], i
else:
current += nums[i]
if current > best:
best, best_start, best_end = current, start, i
return best, nums[best_start:best_end + 1]
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([-3, -1, -2]))
# Daily profit/loss of a shop: best consecutive period
daily = [1200, -800, 300, 1500, -200, -2500, 900, 1100, -100]
best, period = max_subarray(daily)
print("Best period total:", best, "days:", period)Key points
- Extend the current subarray or restart at each element
- One pass: O(n) time, O(1) memory
- Works when all numbers are negative (returns the largest one)
- Track restarts to recover the subarray itself