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
  • 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
    Commented Mar 15, 2013 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
    Commented Mar 16, 2013 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.
    Commented Aug 26, 2013 at 2:11

1 Answer 1

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
  • 1
    $\begingroup$ This algorithm runs in quadratic time, there might be better ones. $\endgroup$ Commented Mar 15, 2013 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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