11
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – frafl Mar 15 '13 at 21:24
  • 2
    $\begingroup$ 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. $\endgroup$ – WilliamKF Mar 16 '13 at 12:18
  • $\begingroup$ 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). $\endgroup$ – D.W. Aug 26 '13 at 2:11
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This algorithm runs in quadratic time, there might be better ones. $\endgroup$ – Yuval Filmus Mar 15 '13 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.