JAVA DP Solution, O(n) runtime and O(1) space, with inline comment


  • 80
    W
    public int rob(int[] num) {
        int rob = 0; //max monney can get if rob current house
        int notrob = 0; //max money can get if not rob current house
        for(int i=0; i<num.length; i++) {
            int currob = notrob + num[i]; //if rob current value, previous house must not be robbed
            notrob = Math.max(notrob, rob); //if not rob ith house, take the max value of robbed (i-1)th house and not rob (i-1)th house
            rob = currob;
        }
        return Math.max(rob, notrob);
    }

  • 2
    M

    JAVA, 0ms, O(n) runtime and O(1) space, DP.

       public int rob(int[] nums) {
            if(nums.length==0) return 0;
            if(nums.length==1) return nums[0];
            int[] dp = {nums[0], Math.max(nums[0], nums[1])};
            int index=0;
            for(int i=2; i<nums.length; i++){
                index = i&1; // i&1 === i%2.  //index^1: 0->1, 1->0.
            	dp[index] = Math.max(nums[i]+dp[index], dp[index^1]); 
            }
    		return Math.max(dp[0], dp[1]);
    	}

  • -1
    A
    This post is deleted!

  • 0

    @alirezag I tried it and it didn't fail.


Log in to reply
 

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