Subsecuencia creciente de longitud máxima
Una subsecuencia creciente de longitud máxima en una secuencia dada es una subsecuencia de elementos que están en orden creciente y que es lo más larga posible dentro de la secuencia original.
Para encontrar la subsecuencia creciente de longitud máxima en una secuencia dada, se puede utilizar un algoritmo dinámico que recorra la secuencia y vaya construyendo una tabla que indique la longitud de la subsecuencia creciente más larga que termina en cada elemento de la secuencia.
Aquí tienes un ejemplo de cómo se puede implementar este algoritmo en Python:
```python
def subsecuencia_creciente_maxima(secuencia):
n = len(secuencia)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if secuencia[i] > secuencia[j]:
dp[i] = max(dp[i], dp[j] + 1)
longitud_maxima = max(dp)
subsecuencia_maxima = []
indice = dp.index(longitud_maxima)
for i in range(indice, -1, -1):
if dp[i] == longitud_maxima and (not subsecuencia_maxima or secuencia[i] < subsecuencia_maxima[-1]):
subsecuencia_maxima.insert(0, secuencia[i])
longitud_maxima -= 1
return subsecuencia_maxima
# Ejemplo de uso
secuencia = [3, 10, 2, 1, 20]
resultado = subsecuencia_creciente_maxima(secuencia)
print(resultado)
```
En este ejemplo, la función `subsecuencia_creciente_maxima` recibe una secuencia y devuelve la subsecuencia creciente de longitud máxima. Puedes probar este código con diferentes secuencias para encontrar la subsecuencia creciente más larga en cada una.