House Robber

You are given a sequence of non-negative integers, where each integer represents the amount of money available in a house. Your task is to determine the maximum amount of money you can rob tonight without alerting the police. The constraint is that adjacent houses cannot be robbed, as this would raise suspicion.

You can solve this problem using dynamic programming. Define a dp array such that \(dp[i]\) represents the maximum amount of money that can be robbed from the first \(i+1\) houses. The recursive relation is given by:

[ dp[i] = \max(dp[i-1],; dp[i-2] + money[i]) ]

with the initial conditions \(dp[0] = money[0]\) and \(dp[1] = \max(money[0],\; money[1])\). Using this approach, you can compute the maximum amount of money that can be robbed without triggering the alarms.

inputFormat

The input is read from stdin and contains the following:

• The first line contains an integer \(n\) which represents the number of houses. If \(n=0\), it indicates an empty list.
• If \(n > 0\), the second line contains \(n\) space-separated integers representing the amount of money in each house.

outputFormat

Output to stdout a single integer, which is the maximum amount of money that can be robbed from the given list of houses under the constraint that adjacent houses cannot be robbed.

5
2 7 9 3 1

12