The houses on a cul-de-sac stand in a ring, and nums[i] is the cash inside house i. Each house shares an alarm with the two houses beside it, so robbing two neighbouring houses on the same night sets it off. Because the street loops round, the first and last houses are neighbours too.
Return the most cash you can take in one night without robbing two neighbouring houses.
On a straight street, 7 + 9 = 16 would be best, but here houses 0 and 3 are neighbours. The best allowed choice is houses 1 and 3: 2 + 9 = 11.
Houses 0 and 3 give 6 + 8 = 14. Adding house 5 would make 16, but house 5 is next to house 0.
With one house there is no neighbour to worry about.
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 1000The ring adds only one rule: house 0 and house n − 1 can't both be robbed. So at least one of them is left alone, and each of those two cases is a plain straight street.
On a straight street, each house's best total comes from the two before it: skip the house and keep the best so far, or rob it on top of the best from two houses back. The ring breaks that in one place only. House 0 and house n - 1 now touch, and the left-to-right pass reaches the last house without knowing whether the first one was taken.
Time O(n)Space O(1)
The full walkthrough and code are part of Premium
11