House Robber

You are given a list of non-negative integers representing the amount of money of each house on a street. Adjacent houses are connected with a security system, so robbing two directly adjacent houses will trigger the alarm. Your task is to determine the maximum amount of money you can rob without alerting the police.

You can formulate the problem using dynamic programming. The recurrence relation is given by:

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

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

inputFormat

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

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

If \(n = 0\), no second line is provided.

outputFormat

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

0

0