House Robber Problem

Given a list of non-negative integers representing the amount of money in each house, determine the maximum amount that can be robbed without ever robbing two adjacent houses. More formally, if you have a list of houses with values \(a_1, a_2, \dots, a_n\), you need to choose a subset of these houses such that no two chosen houses are adjacent, and the sum of the chosen values is maximized. This can be formulated as:

\[ dp(i) = \max\big( dp(i-1),\ dp(i-2) + a_i \big), \quad \text{for } i \ge 2, \] with initial conditions \(dp(0)=a_1\) and \(dp(1)=\max(a_1,a_2)\). The answer will be \(dp(n-1)\), where \(n\) is the number of houses.

Implement an efficient algorithm to solve this problem.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

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

outputFormat

Output a single integer to standard output (stdout) representing the maximum amount of money that can be robbed without alerting the police.

5
2 7 9 3 1

12