Simple c++ Solution with O(n) runtime and O(n) space


  • 0
    L
      As we have finish the House Robber problem before,
    

    so we can just use the same Algorithm to solve this problem.
    The only difference is that in this problem,the houses are a circle,
    so if we want use the previous solution,we need to broke the circle.
    To break the circle,we can separate it into two sub problem by
    robber the last house(nums[len-1]) or not.Then we get two values array,
    one is the value we get if we robber the last house
    and the other is that we do not robber the last house.
    Then just compare these two value ( vec1[len-1] and vec2[len-1]),
    the bigger one is what we want.

    class Solution {
    public:
        int rob(vector<int>& nums) {
            int len=nums.size();
            if(len<1) return 0;
            if(len==1) return nums[0];
            if(len==2) return max(nums[0],nums[1]);
            vector<int>vec1(len),vec2(len);
            //calulate the value if we do not robber the last one house and store in vec1;
            //calulate the value if we do robber the last one house and store in vec2;
            vec1[0]=nums[0];
            vec1[1]=max(nums[0],nums[1]);
            vec2[0]=0;
            vec2[1]=nums[1];
            for(int i=2;i<len-1;i++)
            {
                vec1[i]=max(vec1[i-1],vec1[i-2]+nums[i]);
                vec2[i]=max(vec2[i-1],vec2[i-2]+nums[i]);
            }
            vec1[len-1]=vec1[len-2];//because we do not robber the last house;
            vec2[len-1]=max(vec2[len-2],vec2[len-3]+nums[len-1]);
            return max(vec1[len-1],vec2[len-1]);
        }
    };

  • 0
    W

    Clear idea. A little suggestion is that the line vec2[len-1]=max(vec2[len-2],vec2[len-3]+nums[len-1]); is redundant.


  • 0
    M

    Looks good, but you can improve the the space complexity even more to O(1) constant size if you use ints to keep track of the previous and previous-previous max values (the vectors vec1 and vec2 are unnecessary)


Log in to reply
 

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