Biorąc pod uwagę dwa wektory liczb całkowitych o możliwie nierównych długościach, jak mogę określić maksymalny możliwy wynik z akumulacji wybierając maksimum między odpowiadającymi parami liczb między dwoma wektorami z dodatkowymi zerami wstawionymi do krótszego wektora, aby zrekompensować różnicę wielkości?
Na przykład rozważ następujące dwa wektory jako dane wejściowe:
[8 1 4 5]
[7 3 6]
Dostępne opcje wstawienia zera i wynikowej sumy to:
[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
Dlatego w tym przypadku algorytm powinien zwrócić 25.
Mógłbym to zrobić brutalną siłą, obliczając dla wszystkich permutacji umieszczania zer w mniejszym wektorze (jak właśnie to zrobiono powyżej), ale byłoby to drogo obliczeniowe i najgorsze w przypadku, gdy jeden wektor ma dokładnie połowę wielkości drugiego.
Czy istnieje sposób na obliczenie odpowiedzi w czasie liniowym proporcjonalnym do długości dłuższego wektora, nawet gdy wektory różnią się długością? Jeśli nie, czy możemy zrobić coś lepszego niż liczba wybranych kombinacji czynnikowych?