Back to DSA
House Robber
mediumGiven a row of houses each containing a certain amount of valuables, determine the maximum total value you can collect without selecting two adjacent houses. The values are provided as an integer array.
Examples
Example 1:
Input:
nums = [3,5,1,8]Output:
13Explanation: Choosing house 2 (value 5) and house 4 (value 8) yields 5 + 8 = 13.
Example 2:
Input:
nums = [4,1,2,7,5]Output:
11Explanation: Choosing houses 1, 3, and 5 gives 4 + 2 + 5 = 11.
Hints
class Solution {
public int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}Time complexity
O(n)Space complexity
O(1)