Stable merging two arrays to maximize product of adjacent elements

Question

The following is an interview question which I am unable to answer in a complexity less than an exponential complexity. Though it seems to be an DP problem, I am unable to form the base cases and analyze it properly. Any help is appreciated.

You are given 2 arrays of size 'n' each. You need to stable-merge these arrays such that in the new array sum of product of consecutive elements is maximized.

For example

A= { 2, 1, 5}

B= { 3, 7, 9}

Stable merging A = {a1, a2, a3} and B = {b1, b2, b3} will create an array C with 2*n elements. For example, say C = { b1, a1, a2, a3, b2, b3 } by merging (stable) A and B. Then the sum = b1*a1 + a2*a3 + b2*b3 should be a maximum.

Answer 1

Lets define c[i,j] as solution of same problem but array start from i to end for left. And j to end for right. So c[0,0] will give solution to original problem.

c[i,j] consists of.

1. MaxValue = the max value.
2. NeedsPairing = true or false = depending on left most element is unpaired.
3. Child = [p,q] or NULL = defining child key which ends up optimal sum till this level.

Now defining the optimal substructure for this DP

c[i,j] = if(NeedsPairing) { left[i]*right[j] } + Max { c[i+1, j], c[i, j+1] }

It's captured more in detail in this code.

if (lstart == lend)
{
    if (rstart == rend)
    {
        nodeResult = new NodeData() { Max = 0, Child = null, NeedsPairing = false };
    }
    else
    {
        nodeResult = new NodeData()
        {
            Max = ComputeMax(right, rstart),
            NeedsPairing = (rend - rstart) % 2 != 0,
            Child = null
        };
    }
}
else
{
    if (rstart == rend)
    {
        nodeResult = new NodeData()
        {
            Max = ComputeMax(left, lstart),
            NeedsPairing = (lend - lstart) % 2 != 0,
            Child = null
        };
    }
    else
    {
        var downLef = Solve(left, lstart + 1, right, rstart);

        var lefResNode = new NodeData()
        {
            Child = Tuple.Create(lstart + 1, rstart),
        };

        if (downLef.NeedsPairing)
        {
            lefResNode.Max = downLef.Max + left[lstart] * right[rstart];
            lefResNode.NeedsPairing = false;
        }
        else
        {
            lefResNode.Max = downLef.Max;
            lefResNode.NeedsPairing = true;
        }

        var downRt = Solve(left, lstart, right, rstart + 1);

        var rtResNode = new NodeData()
        {
            Child = Tuple.Create(lstart, rstart + 1),
        };

        if (downRt.NeedsPairing)
        {
            rtResNode.Max = downRt.Max + right[rstart] * left[lstart];
            rtResNode.NeedsPairing = false;
        }
        else
        {
            rtResNode.Max = downRt.Max;
            rtResNode.NeedsPairing = true;
        }

        if (lefResNode.Max > rtResNode.Max)
        {
            nodeResult = lefResNode;
        }
        else
        {
            nodeResult = rtResNode;
        }
    }
}

And we use memoization to prevent solving sub problem again.

Dictionary<Tuple<int, int>, NodeData> memoization = new Dictionary<Tuple<int, int>, NodeData>();

And in end we use NodeData.Child to trace back the path.

Answer 2

For A = {a1,a2,...,an}, B = {b1,b2,...,bn},

Define DP[i,j] as the maximum stable-merging sum between {ai,...,an} and {bj,...,bn}.

(1 <= i <= n+1, 1 <= j <= n+1)

DP[n+1,n+1] = 0, DP[n+1,k] = bk*bk+1 +...+ bn-1*bn, DP[k,n+1] = ak*ak+1 +...+ an-1*an.

DP[n,k] = max{an*bk + bk+1*bk+2 +..+ bn-1*bn, DP[n,k+2] + bk*bk+1}

DP[k,n] = max{ak*bn + ak+1*ak+2 +..+ an-1*an, DP[k+2,n] + ak*ak+1}

DP[i,j] = max{DP[i+2,j] + ai*ai+1, DP[i,j+2] + bi*bi+1, DP[i+1,j+1] + ai*bi}.

And you return DP[1,1].

Explanation: In each step you have to consider 3 options: take first 2 elements from remaining A, take first 2 element from remaining B, or take both from A and B (Since you can't change the order of A and B, you will have to take the first from A and first from B).