Dynamic ProgrammingArray
Houses stand in a row and each holds some money. Adjacent houses have linked alarms, so you cannot rob two houses next to each other. Find the maximum amount you can rob.
Input
Line 1: n. Line 2: the n amounts.
Output
Print the maximum amount of money.
Constraints
1 <= n <= 10^5 0 <= amount <= 10^4
Example 1
Input
4 1 2 3 1
Output
4
Rob houses 1 and 3 for 1 + 3 = 4.
Example 2
Input
5 2 7 9 3 1
Output
12
Rob houses 1, 3 and 5 for 2 + 9 + 1 = 12.