House Robber II -- LeetCode 213

[Question]

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.

[Analysis]
Assume S(0, n) is the largest amount the thief can get from circle houses H[0,..n], and R(x,y) is the largest amount from linear houses H[x, x+1,...y], then
    S(0,n) = max( R(0,n-1), R(1, n-2) + H[n]).

Since R(x,y) can be calculated using the solution in House Robber, S(0,n) is resolved.

[Solution]
//--- Solution #1 ---
class Solution {
    int robber(vector<int>& n, int lf, int rt) {
        int a=0, b=0, c=0;
        for (int i=lf; i<rt; i++) {
            c = max(b, a+n[i]);
            a=b, b=c;
        }
        return c;
    }
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n= nums.size();
        return max( robber(nums, 0, n-1), robber(nums, 1, n-2)+ nums.back());
    }
};

//--- Solution #2 ---
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size()==1) return nums[0];
     
        int a=0, b=nums[0], c=0;
        int x=0, y=0, z=0;
        int res;
        for (int i=1; i<nums.size(); i++) {
            c = max(b, a+nums[i]);  //R0(i)->c, b->R0(i-1)
            z = max(y, x+nums[i]);  //R1(i)->z, x->R1(i-2)

            res = max( x + nums[i], b);

            a=b, b=c;
            x=y, y=z;
        }
        return res;
    }

};