Dos Melodías


Submit solution


Points: 100 (partial)
Time limit: 3.0s
Memory limit: 256M

Authors:
Problem types
Allowed languages
C, C++, Java, Pascal, Python, VB

Alice es una compositora principiante y ahora está lista para crear otra obra maestra. Y no solamente una, sino dos a la misma vez!

Alice tiene una hoja con n notas escritas en esta. Ella quiere seleccionar dos subsecuencias que no sean vacías, no se intersecten, que ambas formen una melodía y la suma de sus tamaños sea máxima.

Una subsecuencia es una secuencia que puede ser derivada de otra eliminando algunos de sus elementos pero sin cambiar el orden de los restantes elementos.

La subsecuencia forma una melodía cuando dos notas adyacentes difieren por 1 ó son congruentes módulo 7.

Tu debes escribir un programa que calcule cuál es la máxima suma del tamaño de dos subsecuencias válidas.

Entrada

La primera línea contiene un número entero n (2 \leq n \leq 5000).

La segunda línea contiene n números enteros a_1, a_2, ..., a_n (1\leq a_i \leq 10^5) las notas escritas en la hoja.

Salida

Imprime la máxima suma del tamaño de dos subsecuencias no vacías, que no se intersecten y que formen una melodía.

Ejemplo #1 de Entrada

4
1 2 4 5

Ejemplo #1 de Salida

4

Ejemplo #2 de Entrada

6
62 22 60 61 48 49

Ejemplo #2 de Salida

5

Explicación

En el primer caso ejemplo las subsecuencias [1, 2] y [4, 5] dan un largo de 4 en total.

En el segundo caso ejemplo las subsecuencias [62, 48, 49] y [60, 61] dan un largo de 5 en total. Si eliges las subsecuencias [62, 61] en el primer lugar entonces la segunda melodía tendrá un tamaño máximo de 2, lo queda el resultado final de 4, que no es máximo.


Comments

There are no comments at the moment.