Maximum subsequence sum such that no three are consecutive

The problem, simply

You get a row of positive numbers. Pick some of them so that you never pick three neighbors in a row. Two neighbors are fine. Give back the biggest sum you can get.

A story to remember it

Picture it

Examples

Way 1: the simple way

Let f(i) be the best sum using items 0 to i. Look at item i and try the three moves.

1. Skip item i: f(i - 1).
2. Take item i only: a[i] + f(i - 2). Item i - 1 is skipped.
3. Take items i and i - 1: a[i] + a[i - 1] + f(i - 3). Item i - 2 is skipped.
4. Small cases: f(-1) = 0, f(0) = a[0], f(1) = a[0] + a[1].

class Solution {
    public int maxSumNoThree(int[] a) {
        return best(a, a.length - 1);
    }

    private int best(int[] a, int i) {
        if (i < 0) return 0;                     // no jars
        if (i == 0) return a[0];
        if (i == 1) return a[0] + a[1];          // two in a row is allowed
        int skip = best(a, i - 1);
        int takeOne = a[i] + best(a, i - 2);
        int takeTwo = a[i] + a[i - 1] + best(a, i - 3);
        return Math.max(skip, Math.max(takeOne, takeTwo));
    }
}

How long it takes: three branches per call, so the tree grows like O(3^n). Extra room: the waiting calls, O(n).

Way 2: the clever way

The same f(i) values are asked over and over. Compute them once, left to right, and keep them in a row called dp.

1. dp[0] = a[0], dp[1] = a[0] + a[1].
2. For each later i, dp[i] is the best of skip, take one, take two, reading dp[i - 1], dp[i - 2] and dp[i - 3] (0 when the index is below 0).
3. The answer is the last box.

The arrows show the three boxes each new box reads.

class Solution {
    public int maxSumNoThree(int[] a) {
        int n = a.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        dp[0] = a[0];
        if (n > 1) dp[1] = a[0] + a[1];
        for (int i = 2; i < n; i++) {
            int skip = dp[i - 1];                                   // leave jar i
            int takeOne = a[i] + dp[i - 2];                         // jar i, not jar i - 1
            int takeTwo = a[i] + a[i - 1] + (i >= 3 ? dp[i - 3] : 0); // jars i - 1 and i
            dp[i] = Math.max(skip, Math.max(takeOne, takeTwo));
        }
        return dp[n - 1];
    }
}

How long it takes: one pass, three looks per box, O(n). Extra room: the dp row, O(n). Only the last three boxes are ever read, so three variables are enough for O(1).

Watch out for

• dp[2] must look at all three pairs: a[0] + a[1], a[0] + a[2] and a[1] + a[2]. The general rule handles it if dp[-1] counts as 0.
• Arrays of length 1 or 2 must not crash on dp[1] or dp[i - 3].
• If negative numbers are allowed, dp[1] = a[0] + a[1] is wrong. Use max over the choices, including taking nothing.

What interviewers ask next

• No two adjacent at all? That is house robber: dp[i] = max(dp[i - 1], a[i] + dp[i - 2]).
• No k in a row? Try "take the last 0, 1, ..., k - 1 items" and skip the one before them. That is O(n * k), or O(n) with a sliding window maximum.
• Another way to see it: choose the cheapest set of items to skip so that every window of three neighbors has at least one skipped item. The answer is the total minus that cost, and that skip problem has its own small DP: skip[i] = a[i] + min(skip[i - 1], skip[i - 2], skip[i - 3]).
• Print which items were picked. Walk back from the end and check which of the three choices made each dp[i].

Remember this

Grown-up words: the jars are array elements, the picked jars form a subsequence, the three moves are the transitions of a 1D DP, and the repeated f(i) calls are overlapping subproblems.