451. No Two Adjacent
A row of n houses each hold some amount of money. You may not take from
two houses that are next to each other.
Print the largest total you can take.
This is the shape almost every linear dynamic programming problem has. At each house there are two futures, and the answer is a maximum over them: take this house and add the best from two back, or skip it and keep the best from one back.
The branch that catches people is the take: adding the best from ONE back silently allows two adjacent houses, produces a larger number, and passes every small test.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ money[i] ≤ 1000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers, the money in each house.
Output
Print one integer: the largest total obtainable with no two adjacent houses.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.