Simple Java Solution using House Robber I Twice.


  • 0
    C

    Use the code from House Robber I twice to solve this problem.
    https://leetcode.com/discuss/30079/c-1ms-o-1-space-very-simple-solution.
    See @jianchao.li.fighter's answer in House Robber I, it is clean and clear.

    public int rob(int[] nums) {
        int n = nums.length;
        if(n==0) return 0;
        if(n==1) return nums[0];
        int sum1 = rob(nums,0,n-1); //if use the first elem, then cannot use the last elem.
        int sum2 = rob(nums,1,n);  //if use the second elem, then can use the last elem.
        return Math.max(sum1,sum2);
    }
    private int rob(int[] nums, int start, int end){ // almost the same as House Robber I
        int pre=0, cur=0;
        for(int i=start;i<end;i++){
            int next = Math.max(nums[i]+pre, cur);
            pre = cur;
            cur = next;
        }
        return cur;
    }
    

Log in to reply
 

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