Maximum Coins Collection

You are given n rooms arranged in a straight line. Each room contains a certain number of coins. Your task is to determine the maximum number of coins you can collect, under the restriction that if you collect coins from a room, you cannot collect coins from its immediately adjacent room. In other words, if you collect coins from room i, you must skip room i+1.

The problem can be solved using dynamic programming. Let \(dp[i]\) denote the maximum number of coins that can be collected from the first \(i+1\) rooms. The recurrence relation is given by:

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

with initial conditions \(dp[0] = coins[0]\) and \(dp[1] = \max(coins[0], coins[1])\) (when \(n \geq 2\)).

inputFormat

The first line of input contains a single integer \(n\) representing the number of rooms.

The second line contains \(n\) space-separated integers where each integer represents the number of coins in each room.

outputFormat

Output a single integer: the maximum number of coins that can be collected following the given restrictions.

## sample

5
3 2 5 10 7

15

</p>