Quel algorithme calculerait le maximum de choix parmi deux ensembles?

Étant donné deux vecteurs d'entiers de longueurs éventuellement inégales, comment puis-je déterminer le résultat maximum possible en accumulant le choix entre des paires de nombres correspondantes entre les deux vecteurs avec des zéros supplémentaires insérés dans le vecteur le plus court pour compenser la différence de taille?

Par exemple, considérez les deux vecteurs suivants comme entrées:

[8 1 4 5]
[7 3 6]

Les choix pour insérer le zéro et la somme résultante sont:

[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

Par conséquent, dans ce cas, l'algorithme doit renvoyer 25.

Je pourrais le faire par force brute en calculant toutes les permutations de placement de zéros dans le plus petit vecteur (comme cela vient d'être fait ci-dessus), mais cela serait coûteux en calcul, et pire dans le cas où un vecteur est exactement la moitié de la taille de l'autre.

Existe-t-il un moyen de calculer la réponse en temps linéaire proportionnel à la longueur du vecteur le plus long même lorsque les vecteurs diffèrent en longueur? Sinon, pouvons-nous faire mieux que le nombre de permutations factorielles choisies?

$z,l$$z$$l$