Same street, same alarm — but now the houses stand in a circle, so the first and last are neighbours too. Given nums where nums[i] is the money in house i, return the most you can take without robbing two adjacent houses.
Examples
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: houses 0 and 2 are adjacent on the circle, so 2+2 is illegal.
Example 2:
Input: nums = [1,2,3,1]
Output: 4
Example 3:
Input: nums = [1]
Output: 1
Example 4:
Input: nums = [200,3,140,20,10]
Output: 340
Explanation: houses 0 and 2; house 4 would close the circle onto house 0.
Constraints
1 <= nums.length <= 100
0 <= nums[i] <= 1000
Prerequisites
Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence. Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.
How to think about it
1. Two Streets, One Rule Optimal
Intuition
The circle adds exactly one constraint: the first and last houses cannot both be robbed. So drop one of them and the problem is the straight street again. Run the previous solution twice — once without the last house, once without the first — and take the better. A single house is its own answer, since both slices would be empty.
Algorithm
1. One house: return it. 2. Solve the straight-street problem on houses 0..n-2. 3. Solve it again on houses 1..n-1. 4. Return the larger.