213

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n == 1) return nums[0];
        return max(rob(0, n-2, nums), rob(1, n-1, nums));
    }

    int rob(int left, int right, vector<int> &nums){
        int rob=0, unrob=0, tmp;
        for(int i=left; i<=right; i++){
            tmp=rob;
            rob = nums[i]+unrob;
            unrob = max(tmp, unrob);
        }
        return max(rob, unrob);
    }
};