House Robber II

1public int rob(int[] nums) {
2    if (nums.length == 1) {
3        return nums[0];
4    }
5
6    // Case 1: Rob houses 0 to n-2
7    int[] dp = new int[nums.length - 1];
8    dp[0] = nums[0];
9    dp[1] = Math.max(nums[0], nums[1]);
10
11    for (int i = 2; i < dp.length; i++) {
12        int rob = dp[i - 2] + nums[i];
13        int notRob = dp[i - 1];
14        dp[i] = Math.max(rob, notRob);
15    }
16
17    int case1Max = dp[dp.length - 1];
18
19    // Case 2: Rob houses 1 to n-1
20    dp = new int[nums.length - 1];
21    dp[0] = nums[1];
22    dp[1] = Math.max(nums[1], nums[2]);
23
24    for (int i = 2; i < dp.length; i++) {
25        int rob = dp[i - 2] + nums[i + 1];
26        int notRob = dp[i - 1];
27        dp[i] = Math.max(rob, notRob);
28    }
29
30    int case2Max = dp[dp.length - 1];
31
32    return Math.max(case1Max, case2Max);
33}