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
2class Solution {
3public:
4 int robLinear(vector<int>& nums, int start, int end) {
5 int prev1 = 0, prev2 = 0;
6 for (int i = start; i < end; i++) {
7 int temp = prev1;
8 prev1 = max(nums[i] + prev2, prev1);
9 prev2 = temp;
10 }
11 return prev1;
12 }
13 int rob(vector<int>& nums) {
14 int n = nums.size();
15 if (n == 1) return nums[0];
16 return max(robLinear(nums, 0, n - 1), robLinear(nums, 1, n));
17 }
18};
19This C++ solution uses a helper function robLinear for computing the linear house rob solution and applies it twice: once excluding the first house and once excluding the last house. It returns the maximum of these two 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.