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 |