Non-Adjacent Loot

Difficulty: 1300 3000 ms 128 MB

dp

Pick a subset of houses with no two adjacent, maximizing the total loot. Print the maximum (picking nothing gives 0).

Input: the first line has N; the second line has the N loot values.

Output: the maximum sum of a no-two-adjacent subset.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ a_i ≤ 10⁴

Sample Tests

4
1 2 3 1

4

3
2 7 9

11

Read the Editorial