Sponsored
Sponsored
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
2
This 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.