Resolvamos este problema con programación dinámica.

Siendo ~dp[x][y]~ la respuesta máxima si una melodía termina en la nota número ~x~ y otra melodía - en la nota número ~y~. ~x~ y ~y~ son indexadas en 1, si alguna de estas es 0, entonces la melodía está vacía.

Cómo vamos a actualizar el valor de ~dp[x][y]?~ Primero que todo, actualizaremos el valor de las valores previos de ~dp~ solo si ~x > y~. Si ~x = y~, entonces la respuesta es cero, y si ~x < y~, entonces tomaremos la respuesta para ~dp[y][x]~.

En segundo lugar, para evitar intersecciones, actualizaremos el valor de ~dp[x][y]~ usando solo valores de ~dp[i][j]~, donde ~i != y~ y ~i < x~. Por qué? Porque si nosotros actualizamos el valor de ~dp[x][y]~ desde alguna ~dp[x][i]~, y ~x > y~, entonces puede llevar a alguna intersección (no podemos asegurar que no usamos ~i~ en la primera melodía).

Como podemos hacer actualizaciones rápidas? Contaremos ~dp~ desde ~y = 0~ hacia ~y = n~. Entonces, mientras contamos ~dp~ para algunas ~y~ específicas, mantendremos dos arreglos:

• ~maxmod[j]~ - el valor máximo de ~dp[i][y]~ encontrado hasta ahora donde ~a[i] mod 7 = j~.
• ~maxnum[j]~ - el valor máximo de ~dp[i][y]~ encontrado hasta ahora donde ~a[i] = j~.

Entonces necesitamos contar ~dp[x][y]~, el cual será el mayor de 4 valores:

• ~maxmod[a[x] mod 7] + 1~ - si añadimos una nota que es congruente módulo 7 con la anterior.
• ~maxnum[a[x] + 1] + 1~ - si añadimos una nota que es menor en 1 a la nota anterior.
• ~maxnum[a[x] - 1] + 1~ - si añadimos una nota que es mayor en 1 a la nota anterior.
• ~dp[0][y] + 1~ - si empezamos una nueva melodía.

Estos valores pueden ser calculados en ~O(n^2)~.

Link del problema en Codeforces