Difícil · PD
Subsecuencia creciente más larga
Una subsecuencia salta elementos pero respeta su orden — de 10 9 2 5 3 7, la cadena 2 3 7 es legal y 3 2 no. Define best[i] como la cadena creciente más larga que termina justo en la posición i, y cada elemento solo pregunta: ¿quién antes que yo era menor, y cuánto medía su mejor cadena?
En una frase<code>best[i] = 1 + max(best[j])</code> sobre j < i con <code>a[j] < a[i]</code> (o 1); la respuesta es el máximo sobre todos los i — un doble bucle O(n²).
El problema
Entrada: La primera línea es n (1 ≤ n ≤ 500). La segunda trae n enteros (−1000 a 1000).
Salida: La longitud de la subsecuencia estrictamente creciente más larga.
Ejemplos:
| Entrada | Salida |
|---|---|
8 | 4 |
4 | 1 |
En el primer ejemplo la respuesta 4 es la cadena 2, 3, 7, 18 (o 2, 5, 7, 18). El segundo ejemplo es el detector de rigor: iguales vecinos no encadenan, así que cuatro 2 dan longitud 1, no 4.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — Fija la posición final
«La subsecuencia creciente más larga» resbala hasta que fijas dónde termina. best[i] = la cadena más larga que termina justo en i convierte la meta vaga en n subpreguntas precisas — y la respuesta real es simplemente la mayor de todas. Este movimiento de «lo mejor que termina aquí» es el mismo que rompió Suma máxima de subarray.
Pista 2 — Cada elemento arranca en 1
Antes de cualquier comparación, best[i] = 1: el elemento solo ya es una cadena de longitud uno. Luego mejórala con el mejor predecesor menor. Dos bugs clásicos rompen esta base: olvidar asignarla (leer el global sin inicializar — este motor no pone arrays a cero) o arrancar best[i] en 0, con lo que la cadena nunca cuenta su propio último elemento.
Pista 3 — Estricto significa estricto
La comparación es a[j] < a[i], no <=. Con vecinos iguales permitidos, el test todo-igual devuelve n en vez de 1 — el segundo ejemplo del juez existe justo para cazar ese carácter.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int a[505], best[505];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int ans = 0;
for (int i = 0; i < n; i++) {
best[i] = 1;
for (int j = 0; j < i; j++) {
if (a[j] < a[i] && best[j] + 1 > best[i]) {
best[i] = best[j] + 1;
}
}
if (best[i] > ans) ans = best[i];
}
cout << ans << endl;
return 0;
}El doble bucle O(n²) es la versión honesta; existe una mejora O(n log n) que guarda, para cada longitud, la cola más pequeña posible — y necesita Búsqueda binaria para colocar nuevos elementos. Entre ambas, fíjate en lo que no cambia: la definición de best[i]. Los algoritmos mejores rara vez sustituyen el significado de una PD; hacen que el mismo significado se consulte más barato.
Análisis profundo
Por qué funciona
Fija el final: best[i] = la cadena estrictamente creciente más larga que termina justo en i. Cada i escanea entonces todo su pasado buscando elementos menores con las mejores cadenas — O(n) predecesores cada uno, O(n²) total — y la respuesta global es el máximo sobre todos los finales. El encuadre «lo mejor que termina aquí» es lo que hace computable la meta vaga.
El coste
O(n²) de tiempo, O(n) de espacio — 500² = 250.000 comparaciones, instantáneo. La mejora O(n log n) guarda la cola mínima por longitud e inserta con búsqueda binaria, pero la definición de la PD sobrevive intacta.
Dónde falla
a[j] <= a[i]en vez de<estricto: el test todo-igual devuelve n en vez de 1 — un carácter, una respuesta errónea.- Olvidar
best[i] = 1antes del escaneo: en este motor el global es basura, y hasta en compiladores reales el caso base es lo que permite que una cadena empiece en cualquier parte. - Informar best[n-1] en vez del máximo sobre todos los i: la cadena más larga puede terminar donde sea (mira el test descendente, donde termina en la posición 0).
Siguiente paso
La misma PD de «terminar aquí» en una dimensión y sin parejas: Suma máxima de subarray. La mejora de velocidad necesita Búsqueda binaria sobre las colas de las cadenas.
Dos cosas para recordar
- best[i] = 1 + la mejor entre predecesores menores; respuesta = máximo sobre finales.
<estricto frente a<=es toda la diferencia entre distintos y no-decrecientes.
🐞 Esta versión falla: ábrela y pruébala
Usa a[j] <= a[i] — los iguales encadenan, así que todo-2 da 4 en vez de 1
#include <iostream>
using namespace std;
int a[505], best[505];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int ans = 0;
for (int i = 0; i < n; i++) {
best[i] = 1;
for (int j = 0; j < i; j++) {
if (a[j] <= a[i] && best[j] + 1 > best[i]) { // bug: not strict
best[i] = best[j] + 1;
}
}
if (best[i] > ans) ans = best[i];
}
cout << ans << endl;
return 0;
}