Question: I was asked this question in an interview, but couldn't figure it out and would like to know the answer.

Suppose we have a list like this:

```
1 7 8 6 1 1 5 0

```

I need to find an algorithm such that it pairs adjacent numbers. The goal is to maximize the benefit but such that only the first number in the pair is counted. 

e.g in the above, the optimal solution is:

```
{7,8} {6,1} {5,0}

```

so when taking only the first one:

```
7 + 6 + 5 = 18.

```

I tried various greedy solutions, but they often pick on `{8,6}` which leads to a non-optimal solution. 

Thoughts?

Answer: 
First, observe that it never makes sense to skip more than one number \*. Then, observe that the answer to this problem can be constructed by comparing two numbers:

* The answer to the subproblem where you skip the first number, and
* The answer to the subproblem where you keep the first number

Finally, observe that the answer to a problem with the sequence of only one number is zero, and the solution to the problem with only two numbers is the first number of the two.

With this information in hand, you can construct a recursive [memoized](http://en.wikipedia.org/wiki/Memoization) solution to the problem, or a dynamic programming solution that starts at the back and goes back deciding on whether to include the previous number or not.

 \* Proof: assume that you have a sequence that produces the max sum, and that it skip two numbers in the original sequence. Then you can add the pair that you skipped, and improve on the answer.
Here is a DP formulation for O(N) solution : -

> 
> MaxPairSum(i) = Max(arr[i]+MaxPairSum(i+2),MaxPairSum(i+1))
> 
> 
> MaxPairSum(i) is max sum for subarray (i,N)
> 
> 
>