What algorithm would compute the maximum choices from two sets?
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?
Asked By : WilliamKF
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10543
Answered By : Yuval Filmus
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.
Post a Comment