Diseño y análisis de algoritmos: casos de estudio

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