Practice › Dynamic Programming
House Robber
Medium · Dynamic Programming · Asked at Amazon, Google, Microsoft, Flipkart
Houses in a row hold some money. You cannot rob two adjacent houses. Print the maximum money you can rob.
Input
First line: n. Second line: n amounts.
Output
The maximum amount.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ amount ≤ 10^4
dp[i] = max(dp[i−1], dp[i−2] + a[i]).
Example 1
Input
4 1 2 3 1
Output
4
Example 2
Input
5 2 7 9 3 1
Output
12
Hints
- For each house: either skip it (keep the best so far) or rob it (its money + the best up to two houses back).
- dp[i] = max(dp[i−1], dp[i−2] + a[i]). Only the last two values are needed.
Approach
Let best be the most money from the houses seen so far, and prevBest the same value one house earlier. For each house x, newBest = max(best, prevBest + x): skip x, or rob it on top of the best total that doesn't use the previous house. Shift the two variables and continue. The total reaches 10^9, which fits in 64 bits comfortably.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long long prevBest = 0, best = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
long long newBest = max(best, prevBest + x);
prevBest = best;
best = newBest;
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
prev_best = best = 0
for x in data[1 : data[0] + 1]:
prev_best, best = best, max(best, prev_best + x)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long prevBest = 0, best = 0;
for (int i = 0; i < n; i++) {
long x = sc.nextLong();
long newBest = Math.max(best, prevBest + x);
prevBest = best;
best = newBest;
}
System.out.println(best);
}
}