Máxima Subsecuencia.

Points: 50 (partial)

Time limit: 1.0s

Memory limit: 256M

Authors:

FrankHG, tomaso

Problem type

Allowed languages

C, C++, Java, Pascal, Python, VB

En IslaInformatiza le gustan los problemas con arreglos así que dado un arreglo de números enteros $a_1, a_2, ..., a_N$ ~a_1, a_2, ..., a_N~ 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: $b_1, b_2, ..., b_{N+1}$ ~b_1, b_2, ..., b_{N+1}~, queremos encontrar la subsecuencia más larga $1 \leq p_1 < p_2 < ... < p_k \leq N+1$ ~1 \leq p_1 < p_2 < ... < p_k \leq N+1~ tal que $(b_{p_{i+1}}-b{p_i})=1$ ~(b_{p_{i+1}}-b{p_i})=1~ para cada $1 \leq j < k$ ~1 \leq j < k~.

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 $[1, 2, 3, 4]$ ~[1, 2, 3, 4]~, algunas posibles subsecuencias podrían ser $[1, 3], [2, 4], [1, 2, 3, 4]$ ~[1, 3], [2, 4], [1, 2, 3, 4]~ y $[1,3, 4]$ ~[1,3, 4]~; otras secuencias como $[4, 1], [1, 2, 2]$ ~[4, 1], [1, 2, 2]~ y $[5]$ ~[5]~ no serían subsecuencias de $[1, 2, 3, 4]$ ~[1, 2, 3, 4]~.

Entrada

En la primera línea de la entrada estándar, se ingresa el número $N$ ~N~ de elementos de la serie. En la línea siguiente, se ingresan $N$ ~N~ números separados por un espacio: los valores de los elementos $a_1, a_2, ..., a_N$ ~a_1, a_2, ..., a_N~.

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

$1 \leq N \leq 5*10^5$ ~1 \leq N \leq 5*10^5~.
$1 \leq a_i \leq 5*10^5$ ~1 \leq a_i \leq 5*10^5~ para cada $i$ ~i~.

Ejemplo de Entrada #1

6
5 1 2 4 5 7

Ejemplo de Salida #1

Explicación del ejemplo: La inserción óptima es agregar un elemento con valor $3$ ~3~ en la posición $4$ ~4~: $[5, 1, 2, 3, 4, 5, 7]$ ~[5, 1, 2, 3, 4, 5, 7]~

Ejemplo de Entrada #2

6
10 2 4 1 9 8

Ejemplo de Salida #2

Explicación del ejemplo: La subsecuencia más larga sería $[2, 3, 4]$ ~[2, 3, 4]~

Comments

3

LeandroGamer commented on May 6, 2024, 11:40 p.m.

Help me with this problem please.

3

eblabrada commented on May 8, 2024, 3:54 a.m.

La idea es utilizar DP, se puede definir la siguiente recurrencia $dp(i, v, k)$ ~dp(i, v, k)~ es la máxima subsecuencia que se puede formar hasta la posición $i$ ~i~ siendo $v$ ~v~ el último valor de esa subsecuencia, insertando $k$ ~k~ números, para este problema $k\le 2$ ~k\le 2~.

Para calcular $dp(i, v, k)$ ~dp(i, v, k)~ se pueden utilizar las siguientes transiciones:

$\displaystyle dp(i,v,0) = \max_{j < i}\{dp(j, v - 1, 0)\} +1$ $\displaystyle dp(i,v,1) = \max(\max_{j < i}\{dp(j, v - 1, 1)\} +1, \max_{j < i}\{dp(j, v - 2, 0)\} +2)$

(1) busca la máxima subsecuencia que termina en una posición $j$ ~j~ anterior y cuyo último valor es $v-1$ ~v-1~ sin inserciones.

(2) busca el máximo entre: la máxima subsecuencia que termina en una posición $j$ ~j~ anterior y cuyo último valor es $v-1$ ~v-1~ con una inserción, y la máxima subsecuencia que termina en una posición $j$ ~j~ anterior y cuyo último valor es $v-2$ ~v-2~ sin inserciones y para hacer la secuencia válida se inserta después de $v-2$ ~v-2~ a $v-1$ ~v-1~ que completa la secuencia.

Esto tiene una complejidad de $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~ 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 $dp(v,k)$ ~dp(v,k)~, y utilizando la misma idea para las transiciones queda en una complejidad de $\mathcal{O}(N)$ ~\mathcal{O}(N)~.