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.

Analysis: Now that the houses are arranged in a circle with the first house being the neighbor for the last one. Robbing the first house means the last one cannot be robbed, vise versa. So totally we have three choices here, 

1. rob the first and don't rob the last house

2. rob the last one and don't rob the first house.

3. neither rob the first one nor the last one

What we do is we take off the first house and last one respectively. Calculate the maximum money we can rob by robbing the rest of the houses. We get two maximum value. Choose the larger one. These two maximum value will cover those three cases above.

1 public class Solution { 2     public int rob(int[] nums) { 3         if (nums==null || nums.length==0) return 0; 4         if (nums.length == 1) return nums[0]; 5          6         //get rid of nums[nums.length-1] 7         int[] dp1 = new int[nums.length]; 8         dp1[0] = nums[0]; 9         for (int i=1; i<=nums.length-2; i++) {10             dp1[i] = Math.max(dp1[i-1], nums[i]+(i>=2? dp1[i-2] : 0));11         }12         13         //get rid of nums[0]14         int[] dp2 = new int[nums.length];15         dp2[1] = nums[1];16         for (int i=2; i<=nums.length-1; i++) {17             dp2[i] = Math.max(dp2[i-1], nums[i]+(i>=3? dp2[i-2] : 0));18         }19         return Math.max(dp1[nums.length-2], dp2[nums.length-1]);20     }21 }