Skills101

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: just x.

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.

Kadane on -2 1 -3 4 -1 2 1 -5 4: the cur row is -2 1 -2 4 3 5 6 1 5 and the best row is -2 1 1 4 4 5 6 6 6; the best sum 6 comes from the subarray 4 -1 2 1

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 cur to 0 before updating best — the order of the two lines matters.
  • In the circular version, forgetting the all-negative case (total − min would be 0 = an empty subarray).
  • Using int when 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 at x.
  • best = the largest cur seen; start both at a[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.

Practice what you learned

📝 Quiz: Kadane's Algorithm5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →