[LeetCode] House Robber II

House Robber II

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.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Solution:
The solution is based on the one for House Robber (House Robber I, from now on). In House Robber I, the houses are arranged in a line, while here in House Robber II, the houses are arranged in a circle.
We number all the n houses from 1 to n. The observation is that we can break the circle into two lines, depending whether we consider house 1.
1) We consider house 1. Then we cannot consider house n. This is a problem instance in House Robber I considering n - 1 houses: house 1, ..., house n - 1.
2) We do not consider house 1. Then we can consider house n. This is a problem instance in House Robber I considering n - 1 houses: house 2, ..., house n.
Taking the maximum of the two problem instances in House Robber I gives us the desired result in House Robber II.

public class Solution {
    private int robAlongALine(int[] nums) {
        int[] max = new int[nums.length];
        max[0] = nums[0];
        max[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            max[i] = Math.max(max[i - 1], max[i - 2] + nums[i]);
        }
        return max[nums.length - 1];
    }
    
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        
        int maxWithFirst = robAlongALine(
                Arrays.copyOfRange(nums, 0, nums.length - 1)
            );
        int maxWithoutFirst = robAlongALine(
                Arrays.copyOfRange(nums, 1, nums.length)
            );
        return Math.max(maxWithFirst, maxWithoutFirst);
    }
}