LeetCode 213: House Robber II
Problem Description
Explanation:
To solve this problem, we can break it down into two subproblems:
- Rob houses from the first house to the second-to-last house.
- Rob houses from the second house to the last house.
We can then apply the House Robber algorithm to each subproblem and return the maximum value obtained from these two solutions.
:
Solutions
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
return Math.max(robHelper(nums, 0, nums.length - 2), robHelper(nums, 1, nums.length - 1));
}
private int robHelper(int[] nums, int start, int end) {
int prev1 = 0, prev2 = 0;
for (int i = start; i <= end; i++) {
int temp = prev1;
prev1 = Math.max(prev2 + nums[i], prev1);
prev2 = temp;
}
return prev1;
}
}Related LeetCode Problems
Loading editor...