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 {
3 private int robLinear(int[] nums, int start, int end) {
4 int prev1 = 0, prev2 = 0;
5 for (int i = start; i < end; i++) {
6 int temp = prev1;
7 prev1 = Math.max(nums[i] + prev2, prev1);
8 prev2 = temp;
9 }
10 return prev1;
11 }
12
13 public int rob(int[] nums) {
14 int n = nums.length;
15 if (n == 1) return nums[0];
16 return Math.max(robLinear(nums, 0, n - 1), robLinear(nums, 1, n));
17 }
18}
19This Java solution follows a similar approach using a helper method robLinear to solve the problem twice by excluding first and last house respectively. It returns the maximal result.
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 {
vector<int> memo;
int robHelper(vector<int>& nums, int start, int end) {
if (start >= end) return 0;
if (memo[start] != -1) return memo[start];
memo[start] = max(nums[start] + robHelper(nums, start + 2, end), robHelper(nums, start + 1, end));
return memo[start];
}
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
memo.assign(nums.size(), -1);
int case1 = robHelper(nums, 0, nums.size() - 1);
memo.assign(nums.size(), -1);
int case2 = robHelper(nums, 1, nums.size());
return max(case1, case2);
}
};
This C++ solution utilizes a memoization vector memo for caching previously calculated outcomes of maximum rob scenario from each house index. The recursive function robHelper operates on ranges excluding the first house once and the last house once, with the optimal result retrieved.