What algorithm would compute the maximum choices from two sets?

Question

Given two vectors of integers of possibly unequal lengths, how can I determine the maximum result possible from accumulating choosing the maximum between corresponding pairs of numbers between the two vectors with extra zeros inserted into the shorter vector to make up for the size difference?

For example, consider the following two vectors as inputs:

[8 1 4 5]
[7 3 6]

The choices for inserting the zero and the resulting sum are:

[0 7 3 6] => Maximums: [8 7 4 6] => Sum is: 25
[7 0 3 6] => Maximums: [8 1 4 6] => Sum is: 19
[7 3 0 6] => Maximums: [8 3 4 6] => Sum is: 21
[7 3 6 0] => Maximums: [8 3 6 5] => Sum is: 22

Therefore, in this case, the algorithm should return 25.

I could do this by brute force by calculating for all permutations of placing zeros into the smaller vector (as just done above) but this would be computationally expensive, and worst in the case when one vector is exactly half the size of the other.

Is there a way to compute the answer in linear time proportional to the length of the longer vector even when the vectors differ in length? If not, can we do better than the number of factorial permutations being chosen?

• frafl: Nice problem, how did you come up with it? Do you have some realistic scenario where adding 0ドル$s in arbitrary positions is fine, but reordering the second vector is not?
• WilliamKF: I'm using this to compute the maximum result of another search algorithm related to ranking how similar two sentences are to each other. Correct, reordering is not acceptable.
• D.W.: Are we promised anything about the difference between the lengths of the vectors? In your example, there's only one missing zero. If you know that the number of missing zeros is small, there are more efficient algorithms (for instance, the dynamic programming algorithm can be made to run in linear time, if the number of missing zeros is a constant).

Answer 1

Hint: Use dynamic programming. For each $z,l,ドル compute the optimal way to insert $z$ zeroes to the prefix of length $l$ of the smaller array.

• Yuval Filmus: This algorithm runs in quadratic time, there might be better ones.