Algorithms
Kadane's Algorithm
Overview
Kadane's Algorithm is an efficient dynamic programming algorithm used to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers.
Algorithm Steps
- Initialize
max_sumandcur_sumto-inf - For each value
vin the array:cur_sum = max(cur_sum + v, v)(extend or start new)max_sum = max(max_sum, cur_sum)(track global maximum)
- Return
max_sum
Complexity
| Metric | Complexity | Reason |
|---|---|---|
| Time Complexity | Single pass through array | |
| Space Complexity | Only tracks current and max sum |
Implementation
def kadane(A: list[int]) -> int:
max_sum = cur_sum = -inf
for v in A:
cur_sum = max(cur_sum + v, v)
max_sum = max(max_sum, cur_sum)
return max_sumExample
A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Walk through:
# v = -2: cur_sum = max(-inf + -2, -2) = -2, max_sum = -2
# v = 1: cur_sum = max(-2 + 1, 1) = 1, max_sum = 1
# v = -3: cur_sum = max(1 + -3, -3) = -2, max_sum = 1
# v = 4: cur_sum = max(-2 + 4, 4) = 4, max_sum = 4
# v = -1: cur_sum = max(4 + -1, -1) = 3, max_sum = 4
# v = 2: cur_sum = max(3 + 2, 2) = 5, max_sum = 5
# v = 1: cur_sum = max(5 + 1, 1) = 6, max_sum = 6
# v = -5: cur_sum = max(6 + -5, -5) = 1, max_sum = 6
# v = 4: cur_sum = max(1 + 4, 4) = 5, max_sum = 6
result = kadane(A) # Returns 6, subarray [4, -1, 2, 1]Key Points
- Greedy/DP approach: at each element, choose to extend or restart
- Initializing with
-infhandles empty subarrays and all-negative arrays - Works in a single pass with no auxiliary data structures
- Can be modified to track subarray indices by recording start/end when
max_sumupdates