Kadanes Algo

The problem, simply

You get a row of whole numbers. Some are positive, some are negative. Pick a stretch of numbers that sit next to each other, with at least one number in it, so that their sum is as big as possible. Give back that sum.

A stretch must be in one piece. You may not skip a number in the middle. A piece like this is called a subarray.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every starting house. From each start, walk to the right, keep a running sum, and remember the biggest sum you see.

1. For each start i, set sum = 0.
2. For each end j from i to the last house, add nums[j] to sum.
3. After each add, compare sum with the best and keep the bigger one.

class Solution {
    public int maxSubArray(int[] nums) {
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {      // where the walk starts
            int sum = 0;
            for (int j = i; j < nums.length; j++) {  // where the walk stops
                sum += nums[j];
                best = Math.max(best, sum);
            }
        }
        return best;
    }
}

How long it takes: there are about n * n / 2 pairs of start and end, so O(n^2). Extra room: two counters, O(1). Adding as we go (instead of summing each stretch from scratch, which would be O(n^3)) is already a small win.

Way 2: the clever way

Walk the street once, carrying one bag. At each house ask one question: is my bag worth keeping?

1. bag is the best sum of a stretch that ends at the current house. best is the biggest bag ever.
2. At house i: if bag is below zero, throw it away and start fresh with nums[i]. Otherwise add nums[i] to the bag.
3. Update best if the bag is bigger.

Why is throwing away a negative bag always right? Any stretch that ends here and starts with that negative piece would be bigger without it. So the best stretch ending here either starts fresh or keeps a bag that is zero or more. This rule is Kadane's algorithm. The green boxes below show the best stretch found so far.

class Solution {
    public int maxSubArray(int[] nums) {
        int bag = nums[0];    // best sum of a stretch that ends here
        int best = nums[0];   // best sum seen anywhere
        for (int i = 1; i < nums.length; i++) {
            if (bag < 0) bag = nums[i];   // a negative bag only hurts: drop it
            else bag += nums[i];          // otherwise keep walking with it
            best = Math.max(best, bag);
        }
        return best;
    }

    // Same walk, but also remember where the best stretch starts and ends.
    public int[] bestStretch(int[] nums) {
        int bag = nums[0], best = nums[0];
        int start = 0, bestStart = 0, bestEnd = 0;
        for (int i = 1; i < nums.length; i++) {
            if (bag < 0) { bag = nums[i]; start = i; }
            else bag += nums[i];
            if (bag > best) { best = bag; bestStart = start; bestEnd = i; }
        }
        return new int[] { bestStart, bestEnd };
    }
}

How long it takes: one walk down the street, O(n). Extra room: two numbers, O(1).

Watch out for

• Some versions of the problem allow an empty stretch. Then the answer is never below 0, and starting at 0 is correct. Ask which version you have.
• If the numbers are huge, the sum can overflow an int. Use long when the problem hints at big values.
• Do not confuse this with "maximum sum of any numbers you like". Skipping is not allowed; the stretch is in one piece.

What interviewers ask next

• Print the stretch, not only the sum. Remember where the current bag started, and copy it into bestStart and bestEnd whenever the best improves, as in bestStretch above.
• The street is a circle. The best stretch either does not wrap (plain Kadane) or wraps, which equals the total minus the worst stretch in the middle (Kadane looking for the minimum). Take the bigger, but if every number is negative, use plain Kadane.
• Maximum product of a stretch. Keep both the biggest and the smallest product ending here, because a negative times a negative becomes big.
• Biggest sum of a rectangle in a 2D grid. Fix a top row and a bottom row, add up each column between them, and run Kadane on those column sums. That is O(rows^2 * cols).
• Can you do it with divide and conquer? Yes: the best stretch is in the left half, the right half, or crosses the middle. That is O(n log n), slower, but it is a common follow up.

Remember this

Grown-up words: the stretch of houses is a subarray, the bag is the best sum ending at index i, and dropping a negative bag is Kadane's algorithm, a tiny 1D dynamic programming with dp[i] = max(nums[i], dp[i-1] + nums[i]).