All patterns
Kadane's Algorithm
Best subarray ending here is either extend or restart.
time O(n)space O(1)
What it is
A tiny dynamic program: the best sum of a subarray ending at i is max(a[i], best_ending_here + a[i]). Track the best over all i. It replaces the O(n²) or O(n³) enumeration of subarrays.
When to reach for it
- Maximum sum contiguous subarray
- Best profit from a single run
- Optimal choice depends only on the previous state
Clues in the problem
- Contiguous and sum-maximizing
- Negative numbers present
Template
def max_subarray(a):cur = best = a[0]for x in a[1:]:cur = max(x, cur + x) # extend or restartbest = max(best, cur)return best
Practice problems
- Maximum Subarray
- Maximum Product Subarray
- Best Time to Buy and Sell Stock
- Maximum Sum Circular Subarray
Common mistakes
- Initializing best to 0, which breaks all-negative arrays
- Not tracking indices when the range is required