House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Analysis

1. Need a helper function to rob in a range from low to high freely
2. Main function:
   1. If rob i=0, cannot rob i = length-1
   2. If not rob i=0, can rob i = length-1
   3. Return the maximum of these two conditions

Code

public class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        if (n==0) {return 0;}
        if (n==1) {return nums[0];}
        if (n==2) {return Math.max(nums[0], nums[1]);}
        return Math.max(helper(nums,0,n-2), helper(nums,0, n-1));
    }

    private int helper(int[] nums, int low, int hi){
        int n=nums.length;
        int sum[] = new int[hi-low+1];
        sum[0] = nums[low];
        sum[1] = Math.max(nums[low], nums[low+1]);
        for (int i=2; i<hi-low+1; i++){
            sum[i] = Math.max(sum[i-2]+nums[low+i], sum[i-1]);
        }
        return sum[hi-low];
    }
}

Reference

Ref1