House Robber Problem

You are given a list of non-negative integers representing the amount of money at each house. Your task 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.

The recurrence relation for the dynamic programming solution is given by:

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

where dp[i] represents the maximum money that can be robbed from the first i+1 houses.

inputFormat

The input is read from standard input (stdin). The first line contains an integer n — the number of houses. The second line contains n space-separated integers representing the amount of money in each house.

outputFormat

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

5
2 7 9 3 1

12