House Robber II
MediumDynamic Programming
Houses are arranged in a circle, and nums[i] is the amount of money in house i. House i is next to house i + 1, and the last house is also next to the first house.
You may rob any set of houses as long as no two robbed houses are next to each other. Return the largest total you can rob.
Example 1
- Input:
- nums = [3, 1, 1, 3, 5]
- Output:
- 6
- Explanation
- In a straight line the best would be 3 + 1 + 5 = 9, but the first house (3) and the last house (5) touch in the circle. The best legal choice is 1 + 5 = 6 (or 3 + 3 = 6).
Example 2
- Input:
- nums = [4, 9]
- Output:
- 9
- Explanation
- The two houses are neighbours, so only one can be robbed; take the 9.
Example 3
- Input:
- nums = [8]
- Output:
- 8
- Explanation
- A single house has no neighbour, so it can be robbed.
Constraints
- 1 ≤
nums.length≤ 100 - 0 ≤
nums[i]≤ 1000