☕ DSA Java Articles

Topics › Arrays › Medium

Kadane's Algorithm, maximum subarray sum

Medium TUF ID 2760 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given an integer array nums, find the contiguous, non-empty subarray with the largest sum and return that sum.

Constraints (LeetCode 53): 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4. Under those limits the answer fits in an int, but the methods here return long so they stay correct for any int input (see the pitfalls).

Example 1

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

Example 2

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

“Subarray” means consecutive positions. That is what separates this problem from “maximum subsequence sum”, which would just add up all positive numbers.

Approach 1: Brute force

Intuition. A subarray is determined by its start i and end j. Enumerate every pair, add up the elements between them, and keep the maximum.

Algorithm.

  1. For every i and every j ≥ i:
  2. Compute sum(nums[i..j]) with a third loop.
  3. Track the maximum.
static long bruteForce(int[] nums) {
    long best = Long.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i; j < nums.length; 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) pairs, each summed in O(n). Space O(1).

The innermost loop recomputes almost the same sum over and over: sum(i..j) and sum(i..j+1) differ by one element.

Approach 2: Better, running sum per start

Intuition. Fix the start i and extend j one step at a time. The sum of nums[i..j] is the sum of nums[i..j-1] plus nums[j], so keep a running total instead of re-adding. That removes the third loop.

Algorithm.

  1. For each start i, set sum = 0.
  2. For j from i to n - 1: sum += nums[j], update the maximum.
static long better(int[] nums) {
    long best = Long.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        long sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];                              // sum of nums[i..j] reuses nums[i..j-1]
            best = Math.max(best, sum);
        }
    }
    return best;
}

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

Still 5 × 10^9 steps for n = 10^5. To go faster we must stop trying every start.

Approach 3: Optimal, Kadane’s algorithm

Intuition. Change the question from “which start and end?” to “what is the best subarray that ends exactly at index i?” Call it endHere(i). Any subarray ending at i is either just [nums[i]], or some subarray ending at i - 1 extended by nums[i]. The best of the second kind uses the best subarray ending at i - 1. So:

endHere(i) = nums[i] + max(0, endHere(i - 1))
answer     = max over i of endHere(i)

In words: carry the previous best-ending-here sum forward only if it is positive. A negative running sum can only drag down whatever comes next, so we drop it and start fresh at the next element. That is the whole algorithm, and it needs only one variable for endHere.

The implementation keeps cur = max(0, endHere(i - 1)). At each element: add nums[i] (now cur is exactly endHere(i)), record it in best, then clamp cur to 0 if it went negative. Recording before clamping is what makes all-negative arrays work: the best is recorded as, say, -1, before cur is reset.

Algorithm.

  1. best = -∞, cur = 0.
  2. For each x: cur += x; best = max(best, cur); if cur < 0, set cur = 0.
  3. Return best.
static long optimal(int[] nums) {
    long best = Long.MIN_VALUE;
    long cur = 0;                                        // best sum of a subarray ending at the current index
    for (int x : nums) {
        cur += x;
        best = Math.max(best, cur);                      // record before resetting, so all-negative arrays work
        if (cur < 0) cur = 0;                            // a negative prefix can only hurt what comes next
    }
    return best;
}

Dry run on Example 1:

i x cur after += x best cur < 0, reset?
0 -2 -2 -2 yes → 0
1 1 1 1 no
2 -3 -2 1 yes → 0
3 4 4 4 no
4 -1 3 4 no
5 2 5 5 no
6 1 6 6 no
7 -5 1 6 no
8 4 5 6 no

The reset at index 2 is where the winning subarray [4, -1, 2, 1] begins.

Complexity. Time O(n): one pass. Space O(1).

Why dropping a negative prefix is always safe. Let P be a piece we could carry into index i, that is, a subarray ending at i - 1. If sum(P) < 0, then for every j ≥ i the subarray nums[i..j] beats P followed by nums[i..j], because it lacks the negative part. So a negative-sum piece is never worth keeping, and the best subarray ending at i either starts fresh at i or extends the best subarray ending at i - 1 when that one is positive. That is the recurrence above. Kadane is therefore a tiny dynamic programme: endHere(i) is the state, and keeping only the latest value is the space optimisation.

Recovering the subarray. Remember the index where cur was last reset (start = i + 1), and when best improves, save (start, i). That turns the same loop into “print the maximum subarray”.

Edge cases and pitfalls