Lesson 2.3 · Arrays

Kadane's Algorithm

The best sum of a contiguous subarray in one pass: at each element, either extend the best subarray ending just before it, or start fresh.

15 min

Think of it like this

You're walking along a road picking up and paying out coins. You carry a bag with your running total. If the bag ever holds a debt (a negative total), it can only hurt whatever comes next, so you drop it and start an empty bag at the next coin.

1.The key question at each index

Define cur as the best sum of a subarray that ends exactly at index i. There are only two choices for that subarray: just a[i] alone, or a[i] added to the best subarray ending at i − 1. So cur = max(a[i], cur + a[i]).

The answer is the largest cur seen at any index. One pass, two variables.

▶ Dry run: Kadane on a mixed arraya = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

-2

↑i

-3

-1

-5

State(vars)

cur = -2best = -2

Step 1/9Start with the first element: cur and best are −2.

2.The code

Start both variables at a[0] (not 0), so an array of only negative numbers returns its largest element instead of 0.

Kadane.java

public class Main {
    static int maxSubArray(int[] a) {
        int 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[]{-3, -1, -2}));
    }
}

Output

6
-1

Remember

cur = best subarray ending at i = max(a[i], cur + a[i]).
best = max over all cur.
Initialise with a[0] so all-negative arrays work.
It's the simplest example of dynamic programming: each state depends only on the previous one.

Common mistakes

Starting best at 0 (wrong for all-negative input).
Confusing subarray (contiguous) with subsequence (any elements in order).

Command Palette

Kadane's Algorithm

1.The key question at each index

2.The code