House Robber Circular

Maximize loot from a circular row of houses without robbing adjacent ones.

dynamic-programming arrays circular maximization

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, given as a list `nums`. All houses are arranged in a circle: the first house is adjacent to the last house. You cannot rob two adjacent houses in the circle. Write a function `rob(nums)` that returns the maximum amount of money you can rob tonight without alerting the police.

- The input list is non-empty. Each element is a non-negative integer.
- If the list has length 1, the answer is just that single amount.
- The function signature is `def rob(nums: list[int]) -> int:`.

You must implement the function yourself. You may use any approach, but it should handle large inputs efficiently.

Constraints

1 <= len(nums) <= 10^5
0 <= nums[i] <= 10^4
Your solution should run in O(n) time and O(1) extra space.

Example

```python
>>> rob([2, 3, 2])
3
>>> rob([1, 2, 3, 1])
4
>>> rob([5])
5
>>> rob([2, 7, 9, 3, 1])
11
```

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Consider breaking the circle: the first and last houses cannot both be robbed. So you can try two cases: exclude the first house, or exclude the last house.

For a linear row of houses, use a two-variable DP: keep the max up to the previous house and the max up to two houses ago.

The answer is the maximum of the two linear scenarios.

Handle the special case of a single house directly.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.