Getting everything ready for you…

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

0s

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

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

  1. For each house: either skip it (keep the best so far) or rob it (its money + the best up to two houses back).
  2. 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);
    }
}

Solve House Robber online · All practice problems