En la permutación hay tres tipos de elementos: los que nunca van a ser records, los que no son records pero pueden serlo y los que lo son.

Si estamos en la posición ~i~ y se quiere clasificar al elemento ~a[i]~ como una de estas tres cosas se puede hacer lo siguiente. Denotemos al máximo elemento desde ~1~ hasta ~i - 1~ como ~x~ y al segundo máximo como ~y~, entonces:

• si ~a[i] > x~ entonces el elemento es un record.
• si ~y < a[i] < x~ entonces el elemento no es un record, pero puede serlo si se borra el elemento ~x~.
• en otro caso el elemento nunca va a ser un record.

La idea es contar para cada elemento cuantos nuevos records se forman al quitarlo, por lo que en el segundo caso se guarda la frecuencia de cada ~x~. Por ejemplo si el elemento ~3~ es el ~x~ en el segundo caso y aparece ~5~ veces significa que al quitarlo existen ~5~ elementos que se convierten en records.

Ahora la solución sería para cada elemento ~a[i]~: la cantidad de elementos que son records más la cantidad de elementos que se vuelven records al quitar a ~a[i]~ menos si ~a[i]~ es un record. Se coge el máximo de estas cantidades y eso es la máxima cantidad de records posible.

Complejidad: ~O(n)~