Dados dos vectores de enteros de longitudes posiblemente desiguales, ¿cómo puedo determinar el resultado máximo posible al acumular la elección del máximo entre los pares de números correspondientes entre los dos vectores con ceros adicionales insertados en el vector más corto para compensar la diferencia de tamaño?
Por ejemplo, considere los siguientes dos vectores como entradas:
[8 1 4 5]
[7 3 6]
Las opciones para insertar el cero y la suma resultante son:
[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
Por lo tanto, en este caso, el algoritmo debería devolver 25.
Podría hacerlo mediante la fuerza bruta calculando todas las permutaciones de colocar ceros en el vector más pequeño (como se acaba de hacer anteriormente), pero esto sería computacionalmente costoso, y lo peor en el caso cuando un vector es exactamente la mitad del tamaño del otro.
¿Hay alguna manera de calcular la respuesta en tiempo lineal proporcional a la longitud del vector más largo, incluso cuando los vectores difieren en longitud? Si no, ¿podemos hacerlo mejor que el número de permutaciones factoriales que se eligen?
fuente
Respuestas:
Sugerencia: use programación dinámica. Para cada , calcule la forma óptima de insertar ceros al prefijo de longitud de la matriz más pequeña.z,l z l
fuente