Maximum sum such that no 2 elements are adjacent

The problem, simply

You get a row of positive numbers. Pick some of them so that no two picked numbers stand next to each other. Make the total as big as you can, and give back that total.

You do not need to say which numbers you picked, only the best total. You may also pick nothing, which gives 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

At each jar you have two choices: take it and jump over the next jar, or skip it and move to the next jar. Try both choices everywhere and keep the best.

1. best(i) is the most candy you can get from jar i to the end.
2. If i is past the end, the answer is 0.
3. Otherwise best(i) = max(arr[i] + best(i + 2), best(i + 1)).

class Solution {
    public int findMaxSum(int[] arr) {
        return best(arr, 0);
    }

    private int best(int[] arr, int i) {
        if (i >= arr.length) return 0;            // no jars left
        int take = arr[i] + best(arr, i + 2);      // open this jar, skip the next
        int skip = best(arr, i + 1);               // leave this jar closed
        return Math.max(take, skip);
    }
}

How long it takes: each call makes two more calls, so the work roughly doubles with every jar, O(2^n). Extra room: the calls pile up as deep as the row is long, O(n).

Way 2: the clever way

The tree asks the same questions over and over. So answer each question once, from left to right, and remember the answers. Even better: each answer only needs the two answers just before it, so two notes are enough.

1. prev1 is the best total using the jars up to the one just before this jar.
2. prev2 is the best total using the jars up to two jars back.
3. At jar i: cur = max(prev1, arr[i] + prev2). Skip the jar and keep prev1, or take it and add it to prev2.
4. Slide the notes: prev2 = prev1, prev1 = cur.
5. At the end, prev1 is the answer.

class Solution {
    public int findMaxSum(int[] arr) {
        int prev2 = 0;   // best total up to two jars back
        int prev1 = 0;   // best total up to the jar just before
        for (int x : arr) {
            int cur = Math.max(prev1, x + prev2);  // skip it, or take it
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

How long it takes: one walk along the row, O(n). Extra room: two notes, O(1).

Watch out for

• Greedy by size fails too, as [2, 9, 10, 9] shows.
• Updating the notes in the wrong order. Compute cur first, then move prev1 into prev2, then put cur into prev1.
• If the numbers can be negative, starting both notes at 0 means "pick nothing" is allowed. If the problem demands at least one pick, return the biggest number when every number is negative.
• Large sums can overflow int. Use long when numbers are big.

What interviewers ask next

• The jars stand in a circle, so the first and last jars touch. Solve twice: once without the last jar, once without the first jar, and take the bigger answer.
• Say which jars to take. Keep the full dp array, then walk back from the end: if dp[i] == dp[i - 1], jar i was skipped, otherwise it was taken and you jump to i - 2.
• The jars are houses on a tree, and a parent and child cannot both be robbed. For each node return two numbers: the best if you take it and the best if you skip it.
• Delete and earn: picking a number x removes all x - 1 and x + 1. Add up points per value, then run this same loop over the values.

Remember this

Grown-up words: the jar row is an array, "take or skip" is a recurrence, remembering answers is dynamic programming, and keeping only the last two answers is the space optimization. Interviewers also call this problem House Robber.