House robber II

The houses sit in a circle, so the first and last are neighbours too. Run house robber twice and keep the better result.

The idea

In a circle, robbing both the first and the last house breaks the no-two-neighbours rule. So either the last house is off limits, or the first house is. Running the ordinary straight-line house robber on each of those two shortened rows and keeping the larger answer covers every safe option.

Code

public static int RobCircle(int[] a) {
    if (a.Length == 1) return a[0];
    int excludeLast = RobLinear(a, 0, a.Length - 2);
    int excludeFirst = RobLinear(a, 1, a.Length - 1);
    return Math.Max(excludeLast, excludeFirst);
}
static int RobLinear(int[] a, int lo, int hi) {
    int prev = 0, cur = 0;
    for (int i = lo; i <= hi; i++) {
        int take = prev + a[i];
        prev = cur;
        cur = Math.Max(cur, take);
    }
    return cur;
}

Tips

• A circle of one house is a special case: there is no neighbour conflict, so just take it.
• Both sub-runs use the exact same straight-line recurrence as house robber; only the index range changes.

In the .NET library

It is tempting to just skip "the smaller of the two ends", but that is not always correct: only trying both full ranges and comparing their best totals is guaranteed to find the true optimum.