# LeetCode House Robber II

LeetCode House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

```class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0)return 0;
if (nums.size() == 1)return nums[0];
int ans1 = 0, ans2 = 0;
vector<vector<int>> dp1(nums.size() + 1, vector<int>(2, 0)), dp2(nums.size() + 1, vector<int>(2, 0));
for (int i = 1; i < nums.size(); ++i) { // 不偷最后一家
dp1[i][0] = max(dp1[i - 1][0], dp1[i - 1][1]);
dp1[i][1] = dp1[i - 1][0] + nums[i - 1];
ans1 = max(ans1, max(dp1[i][0], dp1[i][1]));
}
for (int i = 2; i <= nums.size(); ++i) { // 不偷第一家
dp2[i][0] = max(dp2[i - 1][0], dp2[i - 1][1]);
dp2[i][1] = dp2[i - 1][0] + nums[i - 1];
ans2 = max(ans2, max(dp2[i][0], dp2[i][1]));
}
return max(ans1, ans2);
}
};
```

```class Solution {
private:
int subrob(const vector<int>& nums, int left, int right) {
int robsum = 0, norobsum = 0;
for (int i = left; i <= right; ++i) {
int nrs = max(robsum, norobsum);
int rs = norobsum + nums[i];
norobsum = nrs;
robsum = rs;
}
return max(robsum, norobsum);
}
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0)return 0;
if (n == 1)return nums[0];
return max(subrob(nums, 0, n - 2), subrob(nums, 1, n - 1));
}
};
```