213. House Robber II - cocoder39/coco39_LC GitHub Wiki

int rob(vector<int>& nums) {
        int sz = nums.size();
        if(sz == 0){
            return 0;
        }
        if(sz == 1){
            return nums[0];
        }
        vector<int> rob_unrob0(sz);   // max can get if rob   nums[i] && unrob nums[0] 
        vector<int> rob_rob0(sz);   // max can get if rob   nums[i] && rob   nums[0]
        vector<int> unrob_unrob0(sz); // max can get if unrob nums[i] && unrob nums[0]
        vector<int> unrob_rob0(sz); // max can get if unrob nums[i] && rob   nums[0]
        
        rob_rob0[0] = nums[0];
        rob_unrob0[0] = 0;
        unrob_rob0[0] = 0; //not nums[0]
        unrob_unrob0[0] = 0;
        for (int i = 1; i < sz; i++) {
            if (i != sz - 1) { //last one
                rob_rob0[i] = unrob_rob0[i-1] + nums[i];
            }
            rob_unrob0[i] = unrob_unrob0[i-1] + nums[i];
            unrob_rob0[i] = max(rob_rob0[i-1], unrob_rob0[i-1]);
            unrob_unrob0[i] = max(rob_unrob0[i-1], unrob_unrob0[i-1]);
        }
        return max(rob_unrob0[sz-1], max(unrob_unrob0[sz-1], unrob_rob0[sz-1]));
    }

int rob(vector<int>& nums) {
        int sz = nums.size();
        if(sz == 0){
            return 0;
        }
        if(sz == 1){
            return nums[0];
        }
        
        int rob_rob0 = nums[0];
        int rob_unrob0 = 0;
        int unrob_rob0 = 0; //not nums[0]
        int unrob_unrob0 = 0;
        for (int i = 1; i < sz; i++) {
            int rr = rob_rob0;
            int ru = rob_unrob0;
            int ur = unrob_rob0; 
            int uu = unrob_unrob0;
            if (i != sz - 1) { //last one
                rob_rob0 = ur + nums[i];
            }
            rob_unrob0 = uu + nums[i];
            unrob_rob0 = max(rr, ur);
            unrob_unrob0 = max(ru, uu);
        }
        return max(rob_unrob0, max(unrob_unrob0, unrob_rob0));
    }