House Robber II

mediumDynamic Programming+20 XPTime limit 2s

Same as House Robber, but the houses stand in a circle: the first and the last house are neighbours, so you can't rob both.

Input:

line 1: n
line 2: n amounts

Output: the maximum total.

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

Think about it: break the circle — the answer is the better of "rob houses 0 … n−2" and "rob houses 1 … n−1", each solved with the straight-line version. Don't forget n = 1.

Sample input 1

3
2 3 2

Sample output 1

Sample input 2

4
1 2 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…