0ms O(N) time O(1) space C++ solution


  • 12
    T

    This solution is based on house robber 1. The idea is that either the first house or the last house is not robbed. The final solution is max of (house robber without last element) and (house robber without the first element). Note endIndex is not inclusive in the second rob function.

    class Solution {
    public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        
        return max(rob(nums, 0, nums.size()-1), rob(nums, 1, 0));
    }
    
    int rob(vector<int>& nums, int startIndex, int endIndex) {
        int p = 0, q = 0;
        for (int i = startIndex; i != endIndex; /* do nothing */) {
            int tmp = p;
            p = max(p, q + nums[i]);
            q = tmp;
            i = (i + 1) % nums.size();
        }
        return p;
    }
    };

  • 2
    X

    Thanks for the explanation. However, I follow your idea and write this, it pass all the cases. And seems to be easier to understand, is there any corner case missing for my solution?

    public int rob(int[] nums) {
        if(nums.length<1)return 0;
        if(nums.length==1)return nums[0];
        
        return Math.max(rob2(nums,0,nums.length-1),rob2(nums,1,nums.length));
    }
    
    public int rob2(int[] nums,int start,int end) {
        int a=0, b=0;
        for(int i=start;i<end;i++){
            int max=Math.max(b,a+nums[i]);
            a=b;
            b=max;
        }
        return b;
    }

  • 0
    A

    really awesome


  • 0
    T

    Your solution is better. There is no need to move i like: i = (i + 1) % nums.size();


Log in to reply
 

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