This approach involves splitting the problem into two scenarios: robbing from house 0 to house n-2, and from house 1 to house n-1. The aim is to apply the linear version of the House Robber problem to each scenario separately and then take the maximum of the two resulting summed values.
Time Complexity: O(n).
Space Complexity: O(1).
1
2int robLinear(int* nums, int len) {
3 if (len == 0) return 0;
4 if (len == 1) return nums[0];
5 int prev1 = 0, prev2 = 0;
6 for (int i = 0; i < len; i++) {
7 int temp = prev1;
8 prev1 = (nums[i] + prev2 > prev1) ? nums[i] + prev2 : prev1;
9 prev2 = temp;
10 }
11 return prev1;
12}
13
14int rob(int* nums, int numsSize) {
15 if (numsSize == 1) return nums[0];
16 return (robLinear(nums, numsSize - 1) > robLinear(nums + 1, numsSize - 1))
17 ? robLinear(nums, numsSize - 1)
18 : robLinear(nums + 1, numsSize - 1);
19}
20This C solution defines a helper function robLinear for the simpler linear version of the House Robber problem, then uses this to calculate the maximum rob amount in two scenarios: excluding the first and last house respectively. The final result is the maximum of these two computed values.
This approach implements a memoized version of the dynamic programming solution to avoid recomputing values. We explore two scenarios of the circle, taking into account the cycles explicitly by caching intermediate results.
Time Complexity: O(n).
Space Complexity: O(n) for the memoization array.
1
2class Solution {
3 private int[] memo;
4 private int robHelper(int[] nums, int start, int end) {
5 if (start >= end) return 0;
6 if (memo[start] >= 0) return memo[start];
7 memo[start] = Math.max(nums[start] + robHelper(nums, start + 2, end), robHelper(nums, start + 1, end));
8 return memo[start];
9 }
10
11 public int rob(int[] nums) {
12 if (nums.length == 1) return nums[0];
13 memo = new int[nums.length];
14 Arrays.fill(memo, -1);
15 int case1 = robHelper(nums, 0, nums.length - 1);
16 Arrays.fill(memo, -1);
17 int case2 = robHelper(nums, 1, nums.length);
18 return Math.max(case1, case2);
19 }
20}
21This Java solution uses an integer array memo for caching operations to minimize redundant computations. It features a robHelper private method to recursively determine the maximum amount drawable from specific index ranges. Each side of the circle is evaluated for maximizing results separately.