House Robber: Maximum Treasure

Given n houses in a row, where each house contains a certain amount of treasure, determine the maximum amount of treasure that can be stolen without alerting the police by robbing two adjacent houses. The robber must choose a subset of houses such that no two robbed houses are consecutive, and the sum of the treasures is maximized. This problem can be solved using dynamic programming. For instance, if there are 5 houses with treasure amounts [2, 7, 9, 3, 1], the optimal strategy is to rob houses with treasure 2, 9, and 1, achieving a total of 12.

Note: Make sure to read the input from standard input (stdin) and write your answer to standard output (stdout). Any mathematical formulas, if present, should be written in LaTeX format.

inputFormat

The first line contains an integer n, the number of houses. The second line contains n space-separated integers representing the treasure in each house.

outputFormat

Output a single integer representing the maximum amount of treasure that can be stolen without robbing two adjacent houses.

5
2 7 9 3 1

12