6 3 2 5 9 1 8 4 7
Найдём самую длинную невозрастающую последовательность.

Давайте поддерживать такой массив:
v[i] = на какое максимальное число может заканчиваться
невозрастающая последовательность длины ровно i?

Будем рассматривать числа слева направо и обновлять массив.

Можно ещё думать про расширенную последовательность:
-oo -oo -oo ... -oo 6 3 2 5 9 1 8 4 7 +oo ... +oo +oo +oo

|6 3 2 5 9 1 8 4 7
     0   1   2   3   4   5   6   7   8   9
v = +oo -oo -oo -oo -oo -oo -oo -oo -oo -oo

 6|3 2 5 9 1 8 4 7
     0   1   2   3   4   5   6   7   8   9
v = +oo  6  -oo -oo -oo -oo -oo -oo -oo -oo

 6 3|2 5 9 1 8 4 7
     0   1   2   3   4   5   6   7   8   9
v = +oo  6   3  -oo -oo -oo -oo -oo -oo -oo

 6 3 2|5 9 1 8 4 7
     0   1   2   3   4   5   6   7   8   9
v = +oo  6   3   2  -oo -oo -oo -oo -oo -oo

 6 3 2 5|9 1 8 4 7                             ... 6
     0   1   2   3   4   5   6   7   8   9     ... 6 5
v = +oo  6   5   2  -oo -oo -oo -oo -oo -oo    ... 6 3 2

 6 3 2 5 9|1 8 4 7                             ... 9
     0   1   2   3   4   5   6   7   8   9     ... 6 5
v = +oo  9   5   2  -oo -oo -oo -oo -oo -oo    ... 6 3 2

 6 3 2 5 9 1|8 4 7                             ... 9       ... 6 3 2 1
     0   1   2   3   4   5   6   7   8   9     ... 6 5
v = +oo  9   5   2   1  -oo -oo -oo -oo -oo    ... 6 3 2

 6 3 2 5 9 1 8|4 7                             ... 9       ... 6 3 2 1
     0   1   2   3   4   5   6   7   8   9     ... 9 8
v = +oo  9   8   2   1  -oo -oo -oo -oo -oo    ... 6 3 2

 6 3 2 5 9 1 8 4|7                             ... 9       ... 6 3 2 1
     0   1   2   3   4   5   6   7   8   9     ... 9 8
v = +oo  9   8   4   1  -oo -oo -oo -oo -oo    ... 9 8 4

 6 3 2 5 9 1 8 4 7|                            ... 9       ... 6 3 2 1
     0   1   2   3   4   5   6   7   8   9     ... 9 8
v = +oo  9   8   7   1  -oo -oo -oo -oo -oo    ... 9 8 7

Важное наблюдение:
после добавления каждого числа
менялось ровно одно число в массиве v!

v всегда отсортирован по (нестрогому) убыванию.
Значит, куда поставить число -- узнаём двоичным поиском!
