Leetcode 213 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.

抢劫犯的第二题，第一题题解链接 https://cloud.tencent.com/developer/article/1019125

与第一题不同在于这次是一个换，首尾不能同时抢。

那么可以变通一下，将这个问题转化为0-n-2下标和1-n-1下标两个子问题的最大值问题。

这样就可以保证首尾不会同时被抢，相当于做了两次抢劫犯第一题的过程。

class Solution {
public:
    int rob(vector<int>& nums) {
        int a1 = 0;
        int b1 = 0;
        int a2 = 0;
        int b2 = 0;
        if(nums.size() == 1) return nums[0];
        for(int i = 0; i < nums.size(); i++)
        {
            if(i != nums.size() - 1)
            {
                if(i & 1) a1 = max(a1 + nums[i], b1);
                else b1 = max(b1 + nums[i], a1);
            }
            if(i != 0)
            {
                if(i & 1) a2 = max(a2 + nums[i], b2);
                else b2 = max(b2 + nums[i], a2); 
            }
        }
        return max(max(a1, b1), max(a2, b2)); 
    }
};