打家劫舍 II

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