Easy to Understand Solution in Java - O(n) time and O(1) space - 1ms


  • 1
    A

    The solution is almost the same as the House Robber I solution, except this:

    1. If the first house is robbed, the max at the end (at n=nums.length) has to be the same as it was at n-1.
    2. If the first house is not robbed, the max at n=1 is 0 and we calculate everything else normally.
    3. We return the biggest of the two values.
     public int rob(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }
             
             int prevFirstSum=0;
             int prevLastSum=0;
             
             int currFirstSum=nums[0];
             int currLastSum=0;
             
             for(int i=1; i<nums.length-1; i++){
                 int newFirstSum = Math.max(currFirstSum, prevFirstSum+nums[i]);
                 int newLastSum=Math.max(currLastSum, prevLastSum+nums[i]);
                 prevFirstSum = currFirstSum;
                 prevLastSum= currLastSum;
                 currFirstSum = newFirstSum;
                 currLastSum=newLastSum;
             }
             
             currLastSum=Math.max(currLastSum, prevLastSum+nums[nums.length-1]);
             
             return (currFirstSum>currLastSum)? currFirstSum:currLastSum;
        }
    

  • 0
    P

    O(n) Space I think.


Log in to reply
 

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