213. House Robber II (Medium)

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.

[1, 3, 2, 4, 1]

现在房子排成了一个圆圈，则如果抢了第一家，就不能抢最后一家，因为首尾相连了，所以第一家和最后一家只能抢其中的一家，或者都不抢。那我们这里变通一下，如果我们把第一家和最后一家分别去掉，各算一遍能抢的最大值，然后比较两个值取其中较大的一个即为所求。那我们只需参考之前的House Robber 打家劫舍中的解题方法，然后调用两边取较大值。

Solution 1: DP O(n); O(1)

Run DP on first n - 1 elements and last n - 1 elements respectively, choose the larger one.

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

    public int rob1(int[] nums, int left, int right) {
        int preMax = 0; //dp[i - 2]
        int curMax = 0; //dp[i - 1]
        for (int i = left; i < right; i++) {
            int temp = curMax;
            // dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); //two choices: rob, not rob
            curMax = Math.max(preMax + nums[i], curMax); //dp[i - 1] -> dp[i]
            preMax = temp; //dp[i - 2] -> dp[i - 1]
        }
        return curMax;
    }