House Robber Problem

You are given a row of n houses, where the i-th house contains nums[i] amount of money. Your task is to determine the maximum amount of money you can rob tonight without alerting the police.

The constraint is that you cannot rob two adjacent houses. In other words, if you rob house i, you cannot rob house i-1 or house i+1. The recurrence relation for the dynamic programming solution is given by:

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

Using this relation, you must compute the maximum amount of money you can accumulate from the houses.

inputFormat

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

1. The first line contains a single integer n which is the number of houses.
2. The second line contains n non-negative integers separated by spaces representing the amount of money at each house.

If n is 0, then there are no houses and the output should be 0.

outputFormat

The output is a single integer printed to stdout which represents the maximum money that can be robbed under the given constraints.

4
1 2 3 1

4