☕ DSA Java Articles

Topics › Arrays › Medium

Kadane's Algorithm

Medium TUF ID 29 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a non-empty integer array nums. Return the largest possible sum of a contiguous, non-empty subarray. This is LeetCode’s “Maximum Subarray”, and the linear-time method that solves it is called Kadane’s algorithm.

A frequent variant allows the empty subarray, whose sum is 0; in that variant the answer is max(0, result). The code below implements the classic non-empty version, so an all-negative array returns its largest (least negative) element.

Constraints: 1 ≤ n ≤ 10^5, -10^9 ≤ nums[i] ≤ 10^9. With these bounds a sum can reach 10^14, which does not fit in an int, so the methods return long.

Example 1

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
answer = 6          // [4, -1, 2, 1]

Example 2

nums = [5, 4, -1, 7, 8]
answer = 23         // the whole array

Example 3

nums = [-3, -1, -2]
answer = -1         // every subarray is negative; the single element -1 is the best

Approach 1: Brute force

Intuition. Enumerate every subarray by its start and end, compute its sum with a third loop, and keep the maximum. It is the definition of the problem written as code.

Algorithm.

  1. For every start i and every end j ≥ i:
  2. Sum nums[i..j].
  3. Keep the maximum sum seen.
static long bruteForce(int[] nums) {
    int n = nums.length;
    long best = Long.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long sum = 0;
            for (int k = i; k <= j; k++) sum += nums[k];
            best = Math.max(best, sum);
        }
    }
    return best;
}

Complexity. Time O(n^3): O(n^2) subarrays, each summed in O(n). Space O(1).

Approach 2: Better, running sum per start

Intuition. The innermost loop recomputes almost the same sum over and over. For a fixed start i, the sum of nums[i..j] is the sum of nums[i..j-1] plus nums[j], so keep a running total as j advances. That removes one factor of n.

Algorithm.

  1. For every start i: set sum = 0.
  2. For every end j ≥ i: add nums[j] to sum and update the maximum.
static long better(int[] nums) {
    int n = nums.length;
    long best = Long.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        long sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            best = Math.max(best, sum);
        }
    }
    return best;
}

Complexity. Time O(n^2). Space O(1).

For n = 10^5 this is still about 5 × 10^9 additions. To go faster we must stop considering every start separately.

Approach 3: Optimal, Kadane’s algorithm

Intuition. Scan left to right, carrying current, the sum of the subarray that ends at the present position and that we are still willing to extend. When we reach element x we have a choice: extend the carried subarray (current + x) or start fresh at x. Extending is only worth it if the carried sum is positive; a negative prefix can only drag the total down, so it should be dropped. That is the whole algorithm: add x to current, record current as a candidate answer, and if current has become negative, reset it to 0 so that the next element starts a new subarray.

Why is dropping a negative prefix safe? Suppose the optimal subarray is nums[s..e]. Consider the moment the scan is at s. Either current was just reset to 0 (good, we start exactly at s) or current is non-negative and we extend it, which gives a sum ≥ the sum of nums[s..e] once we reach e; it cannot be strictly larger because nums[s..e] is optimal, so it is equal, and in both cases the answer is recorded when the scan passes e. Formally this is dynamic programming over “best subarray ending at i”: end[i] = max(nums[i], end[i-1] + nums[i]), and the answer is the maximum of all end[i].

Algorithm.

  1. Set best = -∞, current = 0.
  2. For every x: current += x; best = max(best, current); if current < 0, set current = 0.
  3. Return best.
static long optimal(int[] nums) {
    long best = Long.MIN_VALUE, current = 0;
    for (int x : nums) {
        current += x;
        best = Math.max(best, current);
        if (current < 0) current = 0;
    }
    return best;
}

Dry run on nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

x current after add best reset?
-2 -2 -2 yes → 0
1 1 1 no
-3 -2 1 yes → 0
4 4 4 no
-1 3 4 no
2 5 5 no
1 6 6 no
-5 1 6 no
4 5 6 no

Complexity. Time O(n): one pass with constant work per element. Space O(1).

The order of the three statements inside the loop matters. best is updated before the reset, which is what makes the all-negative case work: for [-3, -1, -2] the values -3, -1, -2 are each recorded as candidates before current is cleared, so the answer is -1. Updating best after the reset would wrongly return 0, which is the answer to the “empty subarray allowed” variant instead.

The recurrence form

Many people remember Kadane’s algorithm as the DP recurrence directly. It is the same computation with the reset folded into a max:

static long optimalRecurrence(int[] nums) {
    long best = nums[0], endingHere = nums[0];
    for (int i = 1; i < nums.length; i++) {
        endingHere = Math.max(nums[i], endingHere + nums[i]);
        best = Math.max(best, endingHere);
    }
    return best;
}

endingHere is the best sum of a subarray that ends exactly at i. Choosing nums[i] alone over endingHere + nums[i] is precisely “drop the prefix when it is negative”. This version starts from nums[0], which is why it needs a non-empty array; the reset version uses Long.MIN_VALUE as the initial best and 0 as the initial carry, which amounts to the same thing.

Edge cases and pitfalls