House Robber II

Problem

You are given a list of non-negative integers nums representing values at positions arranged in a circle: position 0 is next to position len(nums) - 1 as well as position 1. Choose a subset of positions to collect from so that no two chosen positions are neighbors on the circle, and return the maximum total you can collect.

• The circle has between 1 and a few hundred positions.
• Each value is a non-negative integer no larger than a few thousand.

Examples

• nums = [5, 9, 4, 8, 3] → 17. Take positions 1 and 3 (9 + 8); position 0 is skipped because it neighbors both of them on the circle.
• nums = [11, 5, 14, 2] → 25. Take positions 0 and 2 (11 + 14); they sit across the circle from each other, not next to it.
• nums = [12] → 12. A single position has no neighbor to conflict with, so it is always taken.

Hints

1. The only thing the circle changes versus a straight line is that the first and last positions now conflict. How many of those two can you take?
2. If you decide up front that position 0 is off-limits, is the remaining problem still circular?
3. Solve the linear problem twice, once with the first position removed and once with the last removed, and take the better of the two.