+3

0, 3, 1, 5, 2, 4, 6, 0, 7 → 0, 3, 4, 8, 5, 7, 9, 0, 7

+3

0, 3, 1, 5, 2, 4, 6, 0, 7 → 0, 3, 4, 8, 5, 7, 9, 0, 10

¡El sufijo solo puede mejorar la respuesta!

-2

1, 5, 7, 6, 9 → 1, 3, 5, 6, 9

-2

1, 5, 7, 6, 9 → -1, 3, 5, 6, 9

+2

1, 5, 7, 6, 9 → 1, 5, 7, 8, 11

¡Basta con considerar sufijos! d = x

Modificando el algoritmo estándar de LIS.

0, 60, 10,|50, ...

1 – 10

2 – 60

Modificando el algoritmo estándar de LIS.

30, 60, 10, 50|, ...

1 – 10

2 – 60 50

El LSD de la derecha. <------ ...,|50, 45, 75, 80

1 – 45

2 – 50

3 – 50

El LSD de la derecha. <------ 30, 60, 10, |50, 45, 75, 80

1 – 10

2 – 60

El LSD de la derecha.

30, 60, 10,|50, 45, 75, 80 1 - 10 ← final más largo con 2 - 60 un número 49 o menor

30, 60, 10, 50, 45, 75, 80 1 – 10 2 – 60 ← Ok si x ≥ 11

Cuando vaya por primera vez desde la izquierda, justo antes de "50" recuerda la longitud de la lista que termina con un número 50 + x-1 o más pequeño.

30, 60, 10,|50, ...

1 - 10

2 - 60