Dos Melodías
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 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 .
La segunda línea contiene números enteros 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 y dan un largo de 4 en total.
En el segundo caso ejemplo las subsecuencias y dan un largo de 5 en total. Si eliges las subsecuencias 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