Rob Houses Placed in a Circle
Houses stand in a circle. You get an array money, where money[i] is the amount you can take from house i.
You may take from any set of houses, but you may not take from two neighbouring houses. House i is a neighbour of house i - 1 and house i + 1. Because the houses form a circle, the first and the last house are also neighbours.
Return the largest total you can take.
Note
If there is only one house, it has no neighbour, so you can take it.
Hint
The first and last house cannot both be taken. So solve the problem for a straight line of houses twice: once without the last house, and once without the first house. For a straight line, the best total up to house i is either the best up to i - 1, or money[i] plus the best up to i - 2.
Examples
Example 1
- Input:
- [6,2,3,7]
- Output:
- 9
Taking houses 0 and 3 (6 + 7) is not allowed, because the first and last houses are neighbours. The best is houses 1 and 3: 2 + 7 = 9.
Example 2
- Input:
- [4,9,5,1,8]
- Output:
- 17
Take houses 1 and 4: 9 + 8 = 17. They are not next to each other in the circle.
Example 3
- Input:
- [12]
- Output:
- 12
With one house, take it.
Constraints
1 <= money.length <= 160 <= money[i] <= 100
Run checks your code against the 3 examples. Submit checks it against all 263 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.