Final del 20/12/19 (Algoritmos III)

Final escrito de Min Chih Lin.

Enunciados

Ejercicio 1

Escribir un algoritmo que utilice la técnica de "programación dinámica" para calcular la subsecuencia creciente máxima de una secuencia de números (el mejor algoritmo conocido es de tiempo $O$(n . log(n)) y usa espacio $O$(n)). Mostrar la correctitud y determinar la complejidad del algoritmo propuesto.