Loading...
Loading...
Loading...
The college fest has a treasure game. There are n rooms in a row, and room i hides p[i] points. A player may enter any rooms, but entering two rooms that are next to each other sets off the alarm, and the player is out.
Vikram wants the most points without setting off the alarm. He may also skip every room. Print the largest total he can collect.
Example 1
Input
5 2 7 9 3 1
Output
12
Rooms 1, 3 and 5 give 2 + 9 + 1 = 12. No other set of rooms gives more.
Example 2
Input
4 2 1 1 2
Output
4
Rooms 1 and 4 give 4. Taking every second room gives only 3.
Try the problem first. Open one hint at a time.
Let best[i] be the most points from the first i rooms only.
For room i there are two choices: skip it and keep best[i - 1], or take it and add p[i] to best[i - 2].
best[0] = 0 (no rooms) and best[1] = p[1]. The answer is best[n].
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor