Find best adjacent pair such that to maximize the sum of the first element

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 1

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 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.

Answer 2

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;
}