Maximum Robbed Amount

You are given a row of houses, where each house contains a non-negative integer representing the amount of money available. However, adjacent houses have connected security systems, and if two directly neighboring houses are robbed, the alarm will be triggered. Your task is to determine the maximum amount of money that can be robbed without triggering the alarm.

The problem can be solved using dynamic programming. The recurrence relation is given by: \(dp[i] = \max(dp[i-1], dp[i-2] + \text{money}_i)\) for \(i \ge 2\), with the base cases \(dp[0] = \text{money}_0\) and \(dp[1] = \max(\text{money}_0, \text{money}_1)\).

inputFormat

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

outputFormat

Output a single integer representing the maximum amount of money that can be robbed without alerting the police.

4
1 2 3 1

4