0ms, O(n) time,O(1) space,C++ elegant solution, easy to understand


  • 0
    P
    class Solution {
    public:
        int rob(vector<int>& nums) {
            int res=0;
            if(nums.empty())    return res;
            nums.push_back(nums[0]);
            res = max(res,robStreet(nums,1,nums.size()-2));//without head and tail,both head and tail are nums[0]
            res = max(res,robStreet(nums,2,nums.size()-3)+nums[0]);//with head and tail
            return res;
        }
       int robStreet(vector<int>& nums,int start,int end){
        if(start>nums.size()-1 || end<0)    return 0;   
        int fn_2=0,fn_1=0,fn=0; 
        for(int i=start;i<=end;i++){
            fn = max(fn_2+nums[i],fn_1);
            fn_2 = fn_1;
            fn_1 = fn;
        }
        return fn;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.