¿Por qué no puedo resolver la subsecuencia creciente más larga simplemente ordenando la secuencia y luego iterando a través de cada elemento asegurándome de que la secuencia siempre esté aumentando?

Hasta ahora, ambas respuestas parecen haber entendido mal la pregunta, así que primero diré cómo la entiendo.

1. Comenzamos con una matriz A [0..n-1].
2. Creamos registros del siguiente tipo: (A [i], i)
3. Ordenamos estos registros de acuerdo con el primer elemento (el valor)
4. Tomamos el primer registro en orden ordenado (el que tiene el valor más pequeño)
5. Procesamos los registros restantes uno a la vez, en orden ordenado. Solo tomamos un registro si tanto su valor como su índice son mayores que el valor y el índice del registro tomado anteriormente.

Este algoritmo creará una secuencia creciente, pero no necesariamente la más larga.
Considere la entrada (10,20,30,0).
Nuestros registros, en orden, serían (0,3), (10,0), (20,1) y (30,2).
Su algoritmo comenzaría tomando (0,3), pero luego no puede tomar ninguno de los tres restantes. Acaba de construir la subsecuencia creciente (0). Sin embargo, el más largo es (10,20,30).

En este punto, puede estar pensando en “arreglar” el algoritmo intentando, uno tras otro, cada registro como el primero en tomar. Esto, por supuesto, aumentaría la complejidad del tiempo a Theta (n ^ 2). Pero, lo que es más importante, aún estaría mal . Este enfoque codicioso es fundamentalmente incorrecto, no hay garantía de que la secuencia creciente que produce sea larga.

• Cómo aprender estructuras de datos y algoritmos de manera efectiva para que pueda ser mejor en la programación competitiva a nivel principiante
• ¿Qué escenario aplica algoritmo y estructura de datos?
• ¿Un árbol de búsqueda binario permite un vértice duplicado?
• En programación, ¿un generador de números aleatorios es realmente aleatorio? ¿O son los números aleatorios generados por un algoritmo oculto?
• Ya tengo 30 años, pero mis habilidades de programación y algoritmo no son lo suficientemente buenas. ¿Qué tengo que hacer?

Aquí hay un contraejemplo más complicado:
(0,20,40,60,70,50,30,10)
Claramente, la mejor solución es (0,20,40,60,70).
Sin embargo:

• Si el algoritmo codicioso comienza con el 0, construirá (0,10)
• Si el algoritmo codicioso comienza con el 20, construirá (20,30)
• … y así.