Java one pass for loop. Clean and easy to understand.


  • 0
    M

    Because it's a circle, so there are two conditions that might have the largest number. One is the largest number from range 0 to range length-2 (excluding last element), and the other is from range 1 to length-1.

        public int rob(int[] nums) {
            int[] excludeLast=new int[nums.length],includeLast=new int[nums.length];
            if(nums.length==0) return 0;
            if(nums.length==1) return nums[0];
            
            for(int i=0;i<nums.length;i++){
                if(i>1){
                    includeLast[i]=Math.max(includeLast[i-1],includeLast[i-2]+nums[i]);
                    excludeLast[i]=Math.max(excludeLast[i-1],excludeLast[i-2]+nums[i]);
                }
                else if(i==1){
                    includeLast[i]=Math.max(includeLast[i-1],nums[i]);
                    excludeLast[i]=Math.max(excludeLast[i-1],nums[i]);
                }
                else{
                    includeLast[i]=0;//range from 1 to length-1 so set element[0] to be 0
                    excludeLast[i]=nums[i];
                }
            }
            
            return Math.max(excludeLast[nums.length-2],includeLast[nums.length-1]);
        }
    

Log in to reply
 

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