Arranged in a circle !! explanation what does it mean


  • 1
    R

    This problem is similar to the previous problem House Robber , with one extra condition that houses are arranged in circle . This condition makes the difference that if we are robbing last house then we can not rob the first house and if we are robbing the first house then we can not rob the last house . this is because first and last houses are neighbor of each other .
    To solve this ques we can think 2 cases --

    case 1 ==> take the first house and skip the last house (take input array from first element to one before last element)======>> houseRob(a,0,a.size()-2)

    case 2 ===> take the last house and skip the first house ( take input array from second element to last element) =======>> houseRob(a,1,a.size()-1)

    Now we have to take the maximum of case 1 and case 2 this will be the answer .

     max(houseRob(a,0,a.size()-2),houseRob(a,1,a.size()-1))
    

    here is the code

    int  houseRob(vector<int>&a , int l ,  int h){
            int oneStepBack = 0; 
            int twoStepBack = 0;
            int MaxRob = 0;
            for(int i=l ; i<=h ; i++){
                MaxRob = max( twoStepBack+a[i] , oneStepBack);
                twoStepBack = oneStepBack;
                oneStepBack = MaxRob;
            }
            return MaxRob;
        }
        int rob(vector<int>& a) {
            if(a.size() == 0) return 0;
            if(a.size() == 1) return a[0];
            return max( houseRob(a , 0 , a.size()-2) , houseRob(a , 1 , a.size()-1));
        }

Log in to reply
 

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