Largest Sum Contiguous Subarray

The problem, simply

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

A stretch of neighbors is called a subarray. This is the maximum subarray problem, and the famous fast answer is Kadane's algorithm.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every starting house. From each start, walk right and keep a running sum. Every running sum is the sum of one stretch, so remember the biggest one you see.

1. For each start from 0 to n - 1, set sum = 0.
2. For each end from start to n - 1, add arr[end] to sum and update best.

class Solution {
    public int maxSubArray(int[] arr) {
        int best = Integer.MIN_VALUE;
        for (int start = 0; start < arr.length; start++) {
            int sum = 0;
            for (int end = start; end < arr.length; end++) {
                sum += arr[end];                 // the stretch start..end
                best = Math.max(best, sum);
            }
        }
        return best;
    }
}

How long it takes: about n * n / 2 stretches, O(n^2). Extra room: two counters, O(1).

Way 2: the clever way

Ask a smaller question at every house: "what is the best stretch that ends right here?" Call it cur. A stretch that ends here either is this number alone, or is the best stretch ending at the house before plus this number. So:

cur = max(arr[i], cur + arr[i])

In kid words: if the bag is negative, throw it away and start fresh. The answer is the biggest cur you ever see. You only need the one before, so one number is enough instead of a whole table.

1. Set cur = best = arr[0].
2. For each next number, set cur = max(arr[i], cur + arr[i]).
3. Set best = max(best, cur).

The second row in the animation is the table dp[i] that cur stands for. The code never stores it.

class Solution {
    public int maxSubArray(int[] arr) {
        int cur = arr[0];     // best stretch that ends at this house
        int best = arr[0];    // best stretch seen anywhere
        for (int i = 1; i < arr.length; i++) {
            cur = Math.max(arr[i], cur + arr[i]);   // start fresh or carry on
            best = Math.max(best, cur);
        }
        return best;
    }

    // Also report where the best stretch starts and ends.
    public int[] maxSubArrayWithRange(int[] arr) {
        int cur = arr[0], best = arr[0];
        int start = 0, bestStart = 0, bestEnd = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > cur + arr[i]) { cur = arr[i]; start = i; }  // fresh start here
            else cur += arr[i];
            if (cur > best) { best = cur; bestStart = start; bestEnd = i; }
        }
        return new int[] { best, bestStart, bestEnd };
    }
}

How long it takes: one look at each number, O(n). Extra room: two numbers, O(1).

Watch out for

• Update best after updating cur, every step, not only when cur grows.
• Big numbers: the sum can pass the int limit. Use long if values or lengths are large.
• Empty input: decide with the interviewer. Usually the row has at least one number.
• To return the stretch itself, remember where the current run started and copy it into the answer when best changes.

What interviewers ask next

• Return the start and end index: see maxSubArrayWithRange.
• The row is a circle (the end wraps to the start): the answer is the bigger of the normal answer and total - (smallest stretch). If all numbers are negative, use the normal answer.
• Smallest sum stretch: same idea with min instead of max.
• Biggest product stretch: keep both the biggest and the smallest product ending here, because a negative times a negative becomes big.
• Biggest sum rectangle in a 2D grid: fix a top row and a bottom row, add up each column between them, and run Kadane on that row of column sums. That costs O(rows^2 * cols).
• Can you do it with divide and conquer? Yes, in O(n log n): the best stretch is in the left half, the right half, or crosses the middle. Kadane is faster.

Remember this

Grown-up words: the stretch of houses is a contiguous subarray, the candy bag is the running sum cur, "best ending here" is the DP state, and the whole trick is Kadane's algorithm.