Dados dois vetores de números inteiros de comprimentos possivelmente desiguais, como posso determinar o resultado máximo possível ao acumular a escolha do máximo entre pares correspondentes de números entre os dois vetores com zeros extras inseridos no vetor mais curto para compensar a diferença de tamanho?
Por exemplo, considere os dois vetores a seguir como entradas:
[8 1 4 5]
[7 3 6]
As opções para inserir o zero e a soma resultante são:
[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
Portanto, nesse caso, o algoritmo deve retornar 25.
Eu poderia fazer isso com força bruta, calculando todas as permutações de colocar zeros no vetor menor (como acabamos de fazer acima), mas isso seria computacionalmente caro e, pior ainda, quando um vetor tiver exatamente a metade do tamanho do outro.
Existe uma maneira de calcular a resposta em tempo linear proporcional ao comprimento do vetor mais longo, mesmo quando os vetores diferem em comprimento? Caso contrário, podemos fazer melhor do que o número de permutações fatoriais sendo escolhidas?
fonte
Respostas:
Dica: use programação dinâmica. Para cada , calcule a maneira ideal de inserir no prefixo do comprimento da matriz menor.z,l z l
fonte