Maximum Gold Collection

You are given \( N \) gold mines, each containing a certain amount of gold. Philip wants to collect as much gold as possible, but he cannot mine from two consecutive mines. In other words, if Philip mines the \( i^{th} \) mine, he must skip the \( (i-1)^{th} \) and \( (i+1)^{th} \) mines.

Objective: Determine the maximum amount of gold that can be collected without mining adjacent mines.

Constraints:

• The first input line contains an integer \( N \), the number of gold mines.
• The second input line contains \( N \) space-separated integers where each integer indicates the amount of gold in the corresponding mine.

Hint: This problem can be efficiently solved using dynamic programming. The recurrence relation is given by:

( dp[i] = \max(\text{Gold}[i] + dp[i-2],\ dp[i-1]) )

where \( dp[i] \) represents the maximum gold that can be collected from the first \( i+1 \) mines.

inputFormat

The input is given via standard input and consists of two lines:

1. The first line contains an integer ( N ) — the number of gold mines.
2. The second line contains ( N ) space-separated integers representing the amounts of gold in each mine.

outputFormat

Output a single integer to standard output representing the maximum amount of gold that can be collected without mining two adjacent mines.## sample

4
1 2 3 1

4