Maximum Treasure Robbery

A notorious thief is planning a heist in a line of houses. Each house has a certain amount of treasure. However, if the thief robs two adjacent houses, an alarm will be set off. Your task is to help the thief determine the maximum amount of treasure that can be stolen without triggering the alarm.

Formally, you are given a positive integer \(n\) which represents the number of houses, and a list of \(n\) non-negative integers \(a_1, a_2, \ldots, a_n\) where \(a_i\) denotes the amount of treasure in the \(i\)-th house. The thief cannot rob two adjacent houses. Compute the maximum amount of treasure that can be robbed.

Hint: Use dynamic programming. Define \(dp[i]\) as the maximum treasure that can be robbed from the first \(i+1\) houses. Then, the recurrence relation is:

[ dp[i] = \max(dp[i-1], dp[i-2] + a_{i+1}) \quad \text{for } i \ge 2 ]

Take care of edge cases when \(n=0\) or \(n=1\).

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer \(n\) (\(0 \le n \le 10^5\)), the number of houses.
• The second line contains \(n\) space-separated non-negative integers representing the amount of treasure in each house. If \(n = 0\), the second line will be empty.

outputFormat

Output a single integer representing the maximum amount of treasure the thief can rob without triggering the alarm. The output should be written to standard output (stdout).

5
2 7 9 3 1

12