AdvancedData Structures & Algorithms · Lesson 20 of 20 · Updated ·
Kadane's Algorithm — Maximum Subarray Sum in O(n)
Problem: given an array of integers (some may be negative), find the largest sum of any contiguous subarray. For [-2, 1, -3, 4, -1, 2, 1, -5, 4] the answer is 6, from [4, -1, 2, 1].
Checking every subarray is O(n²) (or O(n³) if you re-add each one). Kadane's algorithm does it in a single pass, O(n) time and O(1) memory. It is one of the most asked array questions in placement interviews.
1. The idea: extend or restart
Walk left to right and keep cur = the best sum of a subarray that ends exactly here. At each new element x there are only two choices:
- extend the previous best subarray:
cur + x, or - restart a new subarray at
x: justx.
Take the larger: cur = max(x, cur + x). If the sum so far is negative, it can only drag x down — so restart. The answer is the largest cur ever seen.
def max_subarray(a):
cur = best = a[0]
for x in a[1:]:
cur = max(x, cur + x) # extend or restart
best = max(best, cur)
return best
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([5, 4, -1, 7, 8]))
print(max_subarray([-3, -1, -2]))
6
23
-1
Starting with cur = best = a[0] (not 0) handles the all-negative case correctly: the answer is the largest single element, -1, not 0. (Some problems allow an empty subarray with sum 0 — read the statement.)
Why is this correct? Any best subarray ends somewhere. cur at that index is the best sum ending there, because the only way to end at i is either a[i] alone or "best ending at i − 1" plus a[i]. That is a tiny dynamic programming recurrence that only needs the previous value.
2. Returning the subarray itself
Interviewers often follow up with "print the subarray". Remember where the current subarray started, and copy the start and end whenever best improves.
def max_subarray_with_range(a):
cur, best = a[0], a[0]
start = best_l = best_r = 0
for i in range(1, len(a)):
if a[i] > cur + a[i]: # restarting is better
cur, start = a[i], i
else:
cur += a[i]
if cur > best:
best, best_l, best_r = cur, start, i
return best, a[best_l:best_r + 1]
print(max_subarray_with_range([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
(6, [4, -1, 2, 1])
The same in Java
public class Main {
static long maxSubarray(int[] a) {
long cur = a[0], best = a[0];
for (int i = 1; i < a.length; i++) {
cur = Math.max(a[i], cur + a[i]);
best = Math.max(best, cur);
}
return best;
}
public static void main(String[] args) {
System.out.println(maxSubarray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
System.out.println(maxSubarray(new int[]{-8, -3, -6}));
}
}
6
-3
Using long protects against overflow when 10⁵ values of up to 10⁹ are added.
3. Variants interviewers ask next
Maximum circular subarray
The array is a circle, so a subarray may wrap from the end back to the start. The best answer is either a normal subarray (plain Kadane), or a wrapping one — which equals total − (minimum subarray). Run Kadane twice: once for the max, once for the min.
def max_circular(a):
best_max = cur_max = a[0]
best_min = cur_min = a[0]
for x in a[1:]:
cur_max = max(x, cur_max + x); best_max = max(best_max, cur_max)
cur_min = min(x, cur_min + x); best_min = min(best_min, cur_min)
if best_max < 0: # every number negative: wrapping would mean "take nothing"
return best_max
return max(best_max, sum(a) - best_min)
print(max_circular([5, -3, 5]))
print(max_circular([-3, -2, -3]))
10
-2
Maximum product subarray
With products, a negative × negative becomes large. Keep both the largest and the smallest product ending here, and swap them when x is negative.
def max_product(a):
hi = lo = best = a[0]
for x in a[1:]:
if x < 0:
hi, lo = lo, hi
hi = max(x, hi * x)
lo = min(x, lo * x)
best = max(best, hi)
return best
print(max_product([2, 3, -2, 4]))
print(max_product([-2, 3, -4]))
6
24
Buy and sell a stock once
"Maximum profit from one buy and one later sell" is Kadane on the daily differences — or simply track the lowest price so far and the best price − lowest.
Common mistakes
- Starting with
best = 0, which returns 0 for an all-negative array. - Resetting
curto 0 before updatingbest— the order of the two lines matters. - In the circular version, forgetting the all-negative case (
total − minwould be 0 = an empty subarray). - Using
intwhen the sum can exceed about 2.1 × 10⁹.
Quick recap
cur = max(x, cur + x): extend the best subarray ending at the previous index, or restart atx.best= the largestcurseen; start both ata[0].- O(n) time, O(1) memory; it is a one-variable dynamic programming solution.
- Circular:
max(kadane, total − min subarray); product: track both max and min.