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.

Example
nums = [3,6,4], return 6

Notice
This is an extension of House Robber.

public class Solution {
    /**
     * @param nums: An array of non-negative integers.
     * @return: The maximum amount of money you can rob tonight
     */
    public int houseRobber2(int[] nums) {
        // 麻烦的地方在于怎么处理首尾
        // 如果有首的话就不能考虑尾
        // 1 100 3 4 200
        // 用首不用尾 104  不用首用尾 300
        /// 100 1 3 4 200
        // 用首不用尾 104  不用首用尾 203
        // 之前没想清楚的点在于如果是用首不用尾，即便最后没有用首，说明首肯定是小，所以只要给了首机会就行
        // 并不是说非要把首加进去
        if(nums == null || nums.length <= 0) {
            return 0;
        }
        int len = nums.length;
        if(len == 1) 
            return nums[0];
        else if(len == 2) 
            return Math.max(nums[0], nums[1]);
        
        int[] dp1 = new int[len];   // 用首不用尾
        int[] dp2 = new int[len];   // 不用首用尾
        
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < len-1; i++) {
            dp1[i] = Math.max(dp1[i-2] + nums[i], dp1[i-1]);
        }
        dp2[0] = nums[0];
        dp2[1] = nums[1];
        dp2[2] = Math.max(nums[1], nums[2]);
        for(int i = 3; i < len; i++) {
            dp2[i] = Math.max(dp2[i-2] + nums[i], dp2[i-1]);
        }
        return Math.max(dp1[len-2], dp2[len-1]);
    }
}