1 Casos de estudio Estudiaremos tres problemas Subsecuencia de suma máxima Subsecuencia común más larga Multiplicación de matrices
2 Subsecuencia de suma máxima Subsecuencia de suma máxima Dados enteros A1, ., An (posiblemente negativos), encontrar el maximo valor de
Si todos los números son negativos, la subsecuencia de suma máxima es 0
3 Subsecuencia de suma máxima Ejemplo: Secuencia: -2,11,-4,13,-5,-2 Respuesta: 20 Veremos cuatro soluciones distintas para este problema Primera solución (fuerza bruta): Calcular la suma de todas las subsecuencias Quedarse con la suma mayor
4 Subsecuencia de suma máxima Solución 1: Fuerza bruta int maxSum = 0; for( i=0; i< a.length; i++) { for( j=i; j< a.length; j++) { int thisSum = 0; for (k=i; k< =j; k++) thisSum += a[k]; if (thisSum > maxSum) maxSum = thisSum; } }
5 Subsecuencia de suma máxima Tiempo: O(n3)
6 Subsecuencia de suma máxima Segunda solución (mejora fuerza bruta) Notar que
Por lo tanto, el tercer ciclo for se puede eliminar
7 Subsecuencia de suma máxima Solución 2: Mejora a fuerza bruta
int maxSum = 0; for( i=0; i< a.length; i++) { int thisSum = 0; for (j=i; j< =a.length; j++) { thisSum += a[j]; if (thisSum > maxSum) maxSum = thisSum; } }
8 Subsecuencia de suma máxima Tiempo: O(n2) Solución 3: Usando "dividir para reinar" Idea: dividir el problema en dos subproblemas del mismo tamaño Resolver recursivamente Mezclar las soluciones Obtener solución final
9 Subsecuencia de suma máxima Dividiendo el problema Subsecuencia de suma máxima puede estar en tres partes: Primera mitad Segunda mitad Cruza por el medio ambas mitades
10 Subsecuencia de suma máxima Dividiendo el problema Ejemplo:
11 Subsecuencia de suma máxima Dividiendo el problema Ejemplo:
Suma máxima primera mitad: 6
12 Subsecuencia de suma máxima Dividiendo el problema Ejemplo:
Suma máxima segunda mitad: 8
| Página siguiente |