Maximum Sum by Selecting Non-Adjacent Pairs

You are given n numbers arranged in a row. Your task is to select some of these numbers such that the following selection rule is satisfied:

1. Each time you select numbers, you must choose exactly 2 adjacent numbers (i.e. a pair).
2. You are not allowed to select a single number.
3. You are not allowed to end up selecting more than 2 consecutive numbers. In other words, if you choose more than one pair, there must be at least one number between any two selected pairs.

Your goal is to choose the pairs (if any) so that the sum of the selected numbers is maximized.

Note: If n < 2, no pair can be chosen and the answer is 0.

The mathematical recurrence using dp can be written in \(\LaTeX\) as follows:

[ \text{dp}[i] = \max\Bigl(\text{dp}[i-1],; a_{i-1}+a_i + \bigl(i \ge 3 ? \text{dp}[i-3] : 0\bigr)\Bigr), \quad \text{for } i \ge 2, ]

with initial conditions

[ \text{dp}[0]=0, \quad \text{dp}[1]=a_0+a_1. ]

inputFormat

The input consists of two lines:

• The first line contains a single integer n (the number of numbers).
• The second line contains n space-separated integers, representing the array.

outputFormat

Output a single integer, which is the maximum sum obtainable by selecting pairs following the rules.

sample

3
1 2 3

5