Practice › Dynamic Programming
House Robber II
Medium · Dynamic Programming · Asked at Amazon, Google, Microsoft, Adobe
Houses stand in a circle, so the first and last houses are neighbours. You cannot rob two adjacent houses. Print the maximum amount you can rob.
Input
First line: n. Second line: n space-separated integers.
Output
The maximum amount.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ a[i] ≤ 10^4
Either the first house is skipped or the last one is. Solve the straight-line House Robber twice: on a[1..n−1] and on a[0..n−2].
Example 1
Input
3 2 3 2
Output
3
Example 2
Input
4 1 2 3 1
Output
4
Hints
- Because the houses form a circle, you can never rob both house 0 and house n − 1.
- So the answer is the better of two straight-line House Robber problems: houses 1..n−1 and houses 0..n−2. Handle n = 1 separately.
Approach
Linear House Robber with two variables: take (best if the current house is robbed) and skip (best if not): take' = skip + a[i], skip' = max(take, skip). Run it on a[1..n−1] and on a[0..n−2] and print the larger result. With a single house, just rob it.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
long long line(const vector<long long> &a, int l, int r) {
long long take = 0, skip = 0;
for (int i = l; i <= r; i++) {
long long t = skip + a[i];
skip = max(take, skip);
take = t;
}
return max(take, skip);
}
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
if (n == 1) cout << a[0] << "\n";
else cout << max(line(a, 1, n - 1), line(a, 0, n - 2)) << "\n";
return 0;
}Python solution
import sys
def line(b):
take = skip = 0
for x in b:
take, skip = skip + x, max(take, skip)
return max(take, skip)
data = list(map(int, sys.stdin.read().split()))
a = data[1 : 1 + data[0]]
print(a[0] if len(a) == 1 else max(line(a[1:]), line(a[:-1])))Java solution
import java.util.*;
public class Main {
static long line(long[] a, int l, int r) {
long take = 0, skip = 0;
for (int i = l; i <= r; i++) {
long t = skip + a[i];
skip = Math.max(take, skip);
take = t;
}
return Math.max(take, skip);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
System.out.println(n == 1 ? a[0] : Math.max(line(a, 1, n - 1), line(a, 0, n - 2)));
}
}