Problem

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.

Notice

This is an extension of House Robber.

Example

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

Note

因为取了队首就不能取队尾，所以对dp数组循环两次，一个从0取到len-2，一个从1取到len-1，比较两次循环后队尾元素，取较大者。注意，要先讨论当原数组位数小于2时的情况。

Solution

public class Solution {
    public int houseRobber2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i <= len-2; i++) dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
        int res = dp[len-2];
        dp[1] = nums[1];
        dp[2] = Math.max(nums[1], nums[2]);
        for (int i = 3; i <= len-1; i++) dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
        return Math.max(res, dp[len-1]);
    }
}