## [213\. House Robber II](https://leetcode.com/problems/house-robber-ii/)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are **arranged in a circle.** That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given an integer array `nums` representing the amount of money of each house, return _the maximum amount of money you can rob tonight **without alerting the police**_.

**Example 1:**

**Input:** nums = \[2,3,2\]
**Output:** 3
**Explanation:** You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

**Example 2:**

**Input:** nums = \[1,2,3,1\]
**Output:** 4
**Explanation:** Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

**Example 3:**

**Input:** nums = \[1,2,3\]
**Output:** 3

**Constraints:**

- `1 <= nums.length <= 100`
- `0 <= nums[i] <= 1000`

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        if (n == 0) return 0;
        if (n == 1) return nums[0];

        // 搶第一間，但不搶最後一間的情況
        int max1 = helper(nums, 0, n - 1);

        // 不搶第一間，但搶最後一間的情況
        int max2 = helper(nums, 1, n);

        return max(max1, max2);
    }
    int helper(vector<int>& nums, int left, int right) {
        int rob = 0, notRob = 0;
        for (int i = left; i < right; ++i) {
            int temp = rob;
            rob = max(nums[i] + notRob, rob);
            notRob = temp;
        }
        return rob;
    }    
};

:::success
- 時間複雜度：$O(N)$
- 空間複雜度：$O(1)$
:::