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.
⭐ Bonus: a speed test with 100,000 houses earns a star in O(n) time. Trying every subset is exponential and won't finish.
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.