Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Because the houses form a circle, you can never rob both house 0 and house n − 1.
  2. 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)));
    }
}

Solve House Robber II online · All practice problems