A street has n billboard slots in a row. Slot i yields net revenue v_i if rented (this can be negative, if upkeep exceeds income). Zoning rules forbid renting two directly adjacent slots (slot i and slot i+1 cannot both be rented). Choose a subset of slots (possibly none) to maximize total net revenue.
Line 1: an integer n.
Line 2: n space-separated integers v_1 ... v_n (empty if n = 0).
A single integer: the maximum total revenue achievable (renting no slots, for a total of 0, is always allowed).
Example 1
Input
5 3 2 5 10 7
Expected
15
Explanation
Renting slots 1, 3 and 5 (values 3, 5, 7) gives 15, the best non-adjacent selection.
Example 2
Input
3 -5 -2 -8
Expected
0
Explanation
Every slot loses money, so the best choice is to rent nothing, for a total of 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →