House Robbery

You are given a row of houses, each containing a certain amount of money. Your goal is to rob houses in such a way that you maximize the total amount stolen, but you cannot rob any two adjacent houses. Formally, given an integer \(n\) representing the number of houses and an array \(A\) of \(n\) non-negative integers where \(A_i\) is the amount of money in the \(i\)-th house, determine the maximum amount of money that can be stolen.

Dynamic Programming: You can use a dynamic programming approach to solve this problem. Define \(dp[i]\) as the maximum money that can be stolen from the first \(i+1\) houses. The relation is given by:

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

The answer is \(dp[n-1]\). Additionally, handle edge cases where \(n = 0\) or \(n = 1\).

inputFormat

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

1. The first line contains a single integer \(n\), the number of houses.
2. The second line contains \(n\) space-separated integers \(A_0, A_1, \ldots, A_{n-1}\) representing the amount of money in each house. If \(n = 0\), the second line will be omitted.

outputFormat

Output a single integer to standard output (stdout) representing the maximum amount of money that can be stolen without alerting the police by robbing two adjacent houses.

4
1 2 3 1

4