House Robbery Optimization

In this problem, you are given a row of houses, each with a certain amount of money. Your goal is to determine the maximum amount of money you can rob without alerting the police. The constraint is that you cannot rob two adjacent houses.

If the money in the houses is represented as an array \(nums\), then the objective is to compute the maximum sum such that no two consecutive elements are chosen. The recurrence relation can be described as:

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

where \(dp[i]\) represents the maximum amount of money that can be robbed from the first \(i+1\) houses.

This problem tests your ability to apply dynamic programming techniques in a real-world context.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains an integer \(n\) representing the number of houses.
• The second line contains \(n\) space-separated integers representing the amount of money in each house.

If \(n = 0\), then the second line will be empty.

outputFormat

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

## sample

4
1 2 3 1

4