House Robber

You are given a row of n buildings. Each building has a certain amount of money. However, if you rob two adjacent buildings, the alarm will be triggered. Your task is to determine the maximum amount of money you can rob without alerting the security.

The problem can be formulated as follows: Given an array of non‐negative integers \(a_1, a_2, \dots, a_n\) (where \(a_i\) represents the money in the \(i\)-th building), find the maximum sum you can obtain by selecting some of these integers such that no two selected integers are adjacent. This is a classic dynamic programming problem.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer \(n\) (where \(n \ge 0\)) denoting the number of buildings. If \(n > 0\), the second line contains \(n\) space-separated integers representing the amount of money in each building.

outputFormat

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

5
2 7 9 3 1

12