House Robber II
Medium · dynamic programming
The houses on a round village green are arranged in a circle, and nums[i] is the amount of money hidden in house i. House i is next to houses i - 1 and i + 1, and because the green is a circle, the first and last houses are neighbours too. If you take from two neighbouring houses the alarm goes off.
Return the maximum total you can take without ever taking from two neighbouring houses. You may skip any houses you like. If there is only one house, it has no neighbours, so you can take it.
Examples
Example 1
Input: nums = [2, 3, 2]
Output: 3
The first and last houses are neighbours, so the two 2s cannot both be taken. The best is the middle house alone.
Example 2
Input: nums = [1, 2, 3, 1]
Output: 4
Take houses 0 and 2: 1 + 3 = 4. Houses 0 and 3 are neighbours on the circle.
Example 3
Input: nums = [5]
Output: 5
Constraints
- 1 <= len(nums) <= 10^4
- 0 <= nums[i] <= 1000