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

Here's a solution in Clojure, if you're interested in something a little more off the beaten path. It's O(n³), as it just generates all n² stable merges and spends n time summing the products. There's a lot less messing with offsets and arithmetic than the array-based imperative solutions I've seen, which hopefully makes the algorithm stand out more. And it's pretty flexible, too: if you want to, for example, include c2*c3 as well as c1*c2 and c3*c4, you can simply replace (partition 2 coll) with (partition 2 1 coll).

;; return a list of all possible ways to stably merge the two input collections
(defn stable-merges [xs ys]
  (lazy-seq
   (cond (empty? xs) [ys]
         (empty? ys) [xs]
         :else (concat (let [[x & xs] xs]
                         (for [merge (stable-merges xs ys)]
                           (cons x merge)))
                       (let [[y & ys] ys]
                         (for [merge (stable-merges xs ys)]
                           (cons y merge)))))))

;; split up into chunks of two, multiply, and add the results
(defn sum-of-products [coll]
  (apply + (for [[a b] (partition 2 coll)]
             (* a b))))

;; try all the merges, find the one with the biggest sum
(defn best-merge [xs ys]
  (apply max-key sum-of-products (stable-merges xs ys)))

user> (best-merge [2 1 5] [3 7 9])
(2 1 3 5 7 9)

Answer 3

Merge it and sort it. May be merge sort. Sorted array give max value.(Merge is just append the arrays). complexity is nlogn.

Answer 4

One way to solve it by dynamic programming is to always store:

S[ i ][ j ][ l ] = "Best way to merge A[1,...,i] and B[1,...,j] such that, if l == 0, the last element is A[i], and if l == 1, the last element is B[j]".

Then, the DP would be (pseudo-code, insert any number at A[0] and B[0], and let the actual input be in A[1]...A[n], B[1]...B[n]):

S[0][0][0] = S[0][0][1] = S[1][0][0] = S[0][1][1] = 0; // If there is only 0 or 1 element at the merged vector, the answer is 0
S[1][0][1] = S[0][1][1] = -infinity; // These two cases are impossible
for i = 1...n:
    for j = 1...n:
        // Note that the cases involving A[0] or B[0] are correctly handled by "-infinity"
        // First consider the case when the last element is A[i]
        S[i][j][0] = max(S[i-1][j][0] + A[i-1]*A[i], // The second to last is A[i-1].
                         S[i-1][j][1] + B[j]*A[i]); // The second to last is B[j]
        // Similarly consider when the last element is B[j]
        S[i][j][1] = max(S[i][j-1][0] + A[i]*B[j], // The second to last is A[i]
                         S[i][j-1][1] + B[j-1]*B[j]); // The second to last is B[j-1]
 // The answer is the best way to merge all elements of A and B, leaving either A[n] or B[n] at the end.
return max(S[n][n][0], S[n][n][1]);

Answer 5

Define F(i, j) as the maximal pairwise sum that can be achieved by stable merging Ai...An and Bj...Bn.

At each step in the merge, we can choose one of three options:

1. Take the first two remaining elements of A.
2. Take the first remaining element of A and the first remaining element of B.
3. Take the first two remaining elements of B.

Thus, F(i, j) can be defined recursively as:

F(n, n) = 0
F(i, j) = max
(
    AiAi+1 + F(i+2, j), //Option 1
    AiBj + F(i+1, j+1), //Option 2
    BjBj+1 + F(i, j+2)  //Option 3
)

To find the optimal merging of the two lists, we need to find F(0, 0), naively, this would involve computing intermediate values many times, but by caching each F(i, j) as it is found, the complexity is reduced to O(n^2).

Here is some quick and dirty c++ that does this:

#include <iostream>

#define INVALID -1

int max(int p, int q, int r)
{
    return p >= q && p >= r ? p : q >= r ? q : r;
}

int F(int i, int j, int * a, int * b, int len, int * cache)
{
    if (cache[i * (len + 1) + j] != INVALID)    
        return cache[i * (len + 1) + j];

    int p = 0, q = 0, r = 0;

    if (i < len && j < len)
        p = a[i] * b[j] + F(i + 1, j + 1, a, b, len, cache);

    if (i + 1 < len)
        q = a[i] * a[i + 1] + F(i + 2, j, a, b, len, cache);

    if (j + 1 < len)
        r = b[j] * b[j + 1] + F(i, j + 2, a, b, len, cache);

    return cache[i * (len + 1) + j] = max(p, q, r);
}

int main(int argc, char ** argv)
{
    int a[] = {2, 1, 3};
    int b[] = {3, 7, 9};
    int len = 3;

    int cache[(len + 1) * (len + 1)];
    for (int i = 0; i < (len + 1) * (len + 1); i++)
        cache[i] = INVALID;

    cache[(len + 1) * (len + 1)  - 1] = 0;

    std::cout << F(0, 0, a, b, len, cache) << std::endl;
}

If you need the actual merged sequence rather than just the sum, you will also have to cache which of p, q, r was selected and backtrack.

Answer 6

I think it would be better if you provide few more test cases. But I think the normal merging of two arrays similar to merging done in merge sort will solve the problem.

The pseudocode for merging arrays is given on Wiki.

Basically it is the normal merging algorithm used in Merge Sort. In Merge sort the, arrays are sorted but here we are applying same merging algorithm for unsorted arrays.

Step 0: Let i be the index for first array(A) and j be the index for second array(B). i=0 , j=0

Step 1: Compare A[i]=2 & B[j]=3. Since 2<3 it will be the first element of the new merged array(C). i=1, j=0 (Add that number to the new array which is lesser)

Step 2: Again Compare A[i]=1 and B[j]=3. 1<3 therefore insert 1 in C. i++, j=0;

Step 3: Again Compare A[i]=3 and B[j]=3. Any number can go in C(both are same). i++, j=0; (Basically we are increasing the index of that array from which number is inserted)

Step 4: Since the array A is complete just directly insert the elements of Array B in C. Otherwise repeat previous steps.

Array C = { 2, 1, 3, 3, 7,9}

I haven't done much research on it. So if there is any test case which could fail, please provide one.

Answer 7

My solution is rather simple. I just explore all the possible stable merges. Following the working C++ program:

#include<iostream>

using namespace std;

void find_max_sum(int *arr1, int len1, int *arr2, int len2, int sum, int& max_sum){
  if(len1 >= 2)
    find_max_sum(arr1+2, len1-2, arr2, len2, sum+(arr1[0]*arr1[1]), max_sum);
  if(len1 >= 1 && len2 >= 1)
    find_max_sum(arr1+1, len1-1, arr2+1, len2-1, sum+(arr1[0]*arr2[0]), max_sum);
  if(len2 >= 2)
    find_max_sum(arr1, len1, arr2+2, len2-2, sum+(arr2[0]*arr2[1]), max_sum);
  if(len1 == 0 && len2 == 0 && sum > max_sum)
    max_sum = sum;
}

int main(){
  int arr1[3] = {2,1,3};
  int arr2[3] = {3,7,9};
  int max_sum=0;
  find_max_sum(arr1, 3, arr2, 3, 0, max_sum);
  cout<<max_sum<<endl;
  return 0;
}

Answer 8

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