Note:This is an extension ofHouse 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 arearranged 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 tonightwithout alerting the police.

tag: DP

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

    private int helper(int[] nums, int start, int end){
        int ans = 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);

        int pre = 0, cur = nums[start];
        for (int i = start + 1; i <= end; i++){
            int temp = cur;
            cur = Math.max(pre + nums[i], cur);
            pre = temp;
        }

        return cur;
    }
}