Máxima Subsecuencia.
En IslaInformatiza le gustan los problemas con arreglos así que dado un arreglo de números enteros usted puede insertar un nuevo elemento (de cualquier valor) en cualquier posición en el arreglo. El objetivo es maximizar la longitud de la subsecuencia más larga de modo que los valores que contiene sean números consecutivos.
Formalmente, si la nueva secuencia después de insertar un elemento es: , queremos encontrar la subsecuencia más larga tal que para cada .
Una subsecuencia es una secuencia que se obtiene al seleccionar elementos en cualquier posición del arreglo original, manteniendo el orden relativo de los elementos seleccionados. Por ejemplo, dada la secuencia original , algunas posibles subsecuencias podrían ser y ; otras secuencias como y no serían subsecuencias de .
Entrada
En la primera línea de la entrada estándar, se ingresa el número de elementos de la serie. En la línea siguiente, se ingresan números separados por un espacio: los valores de los elementos .
Salida
La salida estándar debe contener un solo número: la longitud de la secuencia más larga de números consecutivos, insertando de manera óptima un nuevo elemento.
Restricciones
- .
- para cada .
Ejemplo de Entrada #1
6
5 1 2 4 5 7
Ejemplo de Salida #1
5
Explicación del ejemplo: La inserción óptima es agregar un elemento con valor en la posición :
Ejemplo de Entrada #2
6
10 2 4 1 9 8
Ejemplo de Salida #2
3
Explicación del ejemplo: La subsecuencia más larga sería
Comments
Help me with this problem please.
La idea es utilizar DP, se puede definir la siguiente recurrencia es la máxima subsecuencia que se puede formar hasta la posición siendo el último valor de esa subsecuencia, insertando números, para este problema .
Para calcular se pueden utilizar las siguientes transiciones:
(1) busca la máxima subsecuencia que termina en una posición anterior y cuyo último valor es sin inserciones.
(2) busca el máximo entre: la máxima subsecuencia que termina en una posición anterior y cuyo último valor es con una inserción, y la máxima subsecuencia que termina en una posición anterior y cuyo último valor es sin inserciones y para hacer la secuencia válida se inserta después de a que completa la secuencia.
Esto tiene una complejidad de lo cual no es suficiente. Pero no es difícil de mejorar, solo es darse cuenta que es suficiente iterar de izquierda a derecha para quitarse el primer estado de la recurrencia con eso la recurrencia quedaría , y utilizando la misma idea para las transiciones queda en una complejidad de .