Find Largest sum contiguous Subarray

The problem, simply

You get an array of whole numbers, some positive, some negative. Pick a stretch of boxes that sit next to each other (at least one box). Give back the biggest total any such stretch can have.

If every number is negative, the answer is the least negative number, because you must pick at least one box.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every start. From each start, add boxes one by one to the right and remember the biggest total you see.

1. For each start i, set sum = 0.
2. For each end j >= i, add arr[j] and update best.

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

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

Way 2: the clever way

At each box, the best stretch that ends right here either continues the best stretch that ended at the box before, or starts fresh at this box. Continue only if the bag before is not negative.

1. bag = arr[0], best = arr[0].
2. For each next box: bag = max(arr[i], bag + arr[i]). This is "drop the bag if it is negative".
3. best = max(best, bag).

class Solution {
    public int maxSubArray(int[] arr) {
        int bag = arr[0];     // best total of a stretch that ends at this box
        int best = arr[0];    // best total seen anywhere
        for (int i = 1; i < arr.length; i++) {
            bag = Math.max(arr[i], bag + arr[i]);   // start fresh or keep going
            best = Math.max(best, bag);
        }
        return best;
    }
}

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

To also return where the stretch is, remember the box where the current bag started, and copy it to bestStart and bestEnd = i whenever best grows. That is what the animation shows.

Watch out for

• Very long arrays of big numbers can overflow int. Use long if the sum can pass about 2 billion.
• Update best after updating bag, so a stretch ending at the current box counts.
• An empty stretch is not allowed unless the problem says so. If it is allowed, the answer is never below 0.

What interviewers ask next

• Return the stretch, not only the sum. Track where the current bag started, as described above.
• The array is a circle (the end connects to the start)? The answer is the bigger of the normal answer and total - (smallest stretch sum). If all numbers are negative, use the normal answer.
• Maximum product instead of sum? Keep both the biggest and the smallest product ending here, because a negative times a negative becomes big.
• A 2D grid: biggest rectangle sum? Fix a top row and a bottom row, add each column between them into one array, and run this on it. O(rows^2 * cols).
• Why does it work? The best stretch ending at i is arr[i] plus the best stretch ending at i - 1, but only if that is positive. This is dynamic programming with one number of memory.

Remember this

Grown-up words: the bag is the best subarray sum ending at the current index, dropping it is the "restart" choice in Kadane's algorithm, and the whole thing is a one variable dynamic programming over the array.