Simple Java Solution


  • 2

    Taking into account this circular constraint, either we rob the house at index 0, or the house at last index n.
    In order to reduce this problem to the simpler problem House Robber I, we need to remove the circular condition.

    If we assume that the house at index 0 is not robbed, then we can compute the maximum robbed value using the same algorithm for the linear problem House Robber I.

    In the same way, we compute the maximum robbed value by assuming that the house at last index n is not robbed.

    Finally we get the maximum between these two computed values, and this will be the maximum robbed value taking into account the circular condition.

    public int subRob(int[] num) {
    	num[num.length-1]=num[num.length-1];
    	num[num.length-2]=Math.max(num[num.length-2],num[num.length-1]);
    	for(int i=num.length-3;i>=0;i--) num[i] = Math.max(num[i]+num[i+2], num[i+1]);
    	return num[0];
    }
    public int rob(int[] nums) {
    	if(nums==null || nums.length==0) return 0;
    	if(nums.length==1) return nums[0];
    	if(nums.length==2) return Math.max(nums[0], nums[1]);
    	return Math.max(subRob(Arrays.copyOfRange(nums, 0, nums.length-1)), subRob(Arrays.copyOfRange(nums, 1, nums.length)));
    }
    

Log in to reply
 

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