Algoritma apa yang akan menghitung pilihan maksimum dari dua set?

Diberikan dua vektor bilangan bulat dengan panjang yang mungkin tidak sama, bagaimana saya bisa menentukan hasil maksimum dari akumulasi memilih maksimum antara pasangan angka yang sesuai antara dua vektor dengan nol tambahan dimasukkan ke dalam vektor yang lebih pendek untuk menebus perbedaan ukuran?

Misalnya, pertimbangkan dua vektor berikut sebagai input:

[8 1 4 5]
[7 3 6]

Pilihan untuk memasukkan nol dan jumlah yang dihasilkan adalah:

[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

Oleh karena itu, dalam hal ini, algoritme harus mengembalikan 25.

Saya bisa melakukan ini dengan kekerasan dengan menghitung untuk semua permutasi menempatkan nol ke dalam vektor yang lebih kecil (seperti yang baru saja dilakukan di atas) tetapi ini akan menjadi mahal secara komputasi, dan yang terburuk dalam kasus ketika satu vektor persis setengah ukuran yang lain.

Apakah ada cara untuk menghitung jawaban dalam waktu linier sebanding dengan panjang vektor yang lebih panjang bahkan ketika vektor-vektor panjangnya berbeda? Jika tidak, dapatkah kita melakukan lebih baik daripada jumlah permutasi faktorial yang dipilih?

Petunjuk: Gunakan pemrograman dinamis. Untuk setiap , hitung cara optimal untuk memasukkan nol ke awalan panjang dari array yang lebih kecil.$z,l$$z$$l$