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 всегда отсортирован по (нестрогому) убыванию. Значит, куда поставить число -- узнаём двоичным поиском!