House Robber Problem

You are given a list of non-negative integers representing the amount of money in each house along a street. A thief is planning to rob these houses, but cannot rob two adjacent houses because they would trigger an alarm.

Your task is to compute the maximum amount of money the thief can steal without robbing two consecutive houses.

The problem can be solved using dynamic programming. The recurrence relation is given by \( dp_i = \max(dp_{i-1}, dp_{i-2} + money[i]) \), where \( dp_i \) represents the maximum money that can be collected up to house \( i \).

inputFormat

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

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

outputFormat

Output a single integer to stdout representing the maximum amount of money the thief can rob without alerting the police.

5
2 7 9 3 1

12