Java easy O(n) solution with explanation


  • 0
    A

    At each house the robber decides whether to rob that house or skip it. If he robs it, he can rob the one before it.
    Therefore, we can use below equation -

    result[i]=Math.max(nums[i]+result[i-2],result[i-1]);

    Since, no backtracking is required, the same input array can be used to store the results.

    The first if statement is to handle edge cases.

    public class Solution {
        public int rob(int[] nums) {
            
            if(nums.length<=2)
                return max(nums);
            else
                nums[1]=Math.max(nums[0],nums[1]);
    
                for(int i=2;i<nums.length;i++)
                    nums[i]=Math.max(nums[i]+nums[i-2],nums[i-1]);
            
                return nums[nums.length-1];
        }
        
        public int max(int[] nums){
            int max=0;
            for(int i=0;i<nums.length;i++)
                if(nums[i]>max)
                    max=nums[i];
            return max;        
        }
    }
    

Log in to reply
 

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