The houses on a cul-de-sac stand in a circle: house i is next to houses i - 1 and i + 1, and the last house is next to the first. nums[i] is the cash in house i. You may take the cash from any set of houses as long as no two chosen houses are neighbours. Return the largest total you can collect.
Write rob_circle(nums: list[int]) -> int.
rob_circle([3, 5, 3]) # 5 the two 3s are neighbours across the wrap
rob_circle([2, 7, 9, 3, 1]) # 11 2 + 9 (adding the last house would put it next to house 0)
rob_circle([6, 2, 1, 7, 3]) # 13 6 + 7
rob_circle([8]) # 8
Constraints: 1 <= len(nums) <= 10^5, 0 <= nums[i] <= 10^4. A single house is its own circle: you can take it.
Trying every subset is exponential; aim for O(n) time and O(1) extra space.
Show hint
The first and last houses can't both be taken, so at least one of them is left out. Solve the straight-street version twice.