House Robber II

Problem

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.

Solution

public class Solution {
    public int rob(int[] nums) {
        if (nums == null) return 0; //No need to check nums.length == 0, cause the method will return 0
        if (nums.length == 1) return nums[0]; //This corner case need to be checked, cause the method cannot return correct result
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }

    private int rob(int[] nums, int s, int e) {
        int rob = 0, noRob = 0;
        for (int i = s; i <= e; i++) {
            int temp = noRob;
            noRob = Math.max(rob, noRob);
            rob = nums[i] + temp;
        }
        return Math.max(rob, noRob);
    }
}

Analysis

We divide this robbing circular houses problem to robbing regular houses.
We first modify our regular rob method and add s (start) and e(end) parameters.
Then in main method, we return the max value of robbing first house or robbing second house.
Those two cases will cover all situations, hence we can guarantee our algorithm works.