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: 
A simple dynamic programming problem. Starting from one specific index, we can **either** *make a pair* at current index, or *skip* to the next index:

```
int []dp;//Array to store result of sub-problem
boolean[]check;//Check for already solve sub-problem

public int solve(int index, int []data){
    if(index + 1 >= data.length){//Special case,which cannot create any pair
        return 0;
    }
    if(check[index]){//If this sub-problem is solved before, return the value
        return dp[index];
    }
    check[index] = true;
    //Either make a pair at this index, or skip to next index
    int result = max(data[index] + solve(index + 2, data) , solve(index + 1,data));
    return dp[index] = result;
}

```
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)
> 
> 
>