House Robber

mediumDynamic Programming+20 XPTime limit 2s

Houses stand in a row; house i holds a[i] rupees. You cannot rob two adjacent houses (the alarm goes off). What is the most you can collect?

Input:

line 1: n
line 2: n amounts

Output: the maximum total.

Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ a[i] ≤ 10⁴.

Think about it: at each house choose: skip it (keep the best so far) or rob it (best up to two houses back + a[i]). best[i] = max(best[i−1], best[i−2] + a[i]).

Sample input 1

4
1 2 3 1

Sample output 1

Sample input 2

5
2 7 9 3 1

Sample output 2

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…