House Robber Problem

You are a professional thief planning to rob houses along a street and maximize the amount of money stolen. Each house contains a non-negative amount of money. However, if two adjacent houses are robbed, the alarm will be triggered, and the police will be alerted.

More formally, given an array of non-negative integers \(nums\), where each element represents the amount of money in a house, determine the maximum amount of money you can rob without ever robbing two consecutive houses. The relation for the dynamic programming solution is given by:

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

with base cases \(dp[0] = nums[0]\) and \(dp[1] = \max(nums[0], nums[1])\). If there are no houses, the answer is 0.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer \(n\) (0 ≤ \(n\) ≤ 1000), representing the number of houses.
• The second line contains \(n\) space-separated integers, with each integer representing the amount of money in a 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.

## sample

0

0

</p>