Алгоритм определения наибольшей возрастающей подпоследовательности?

Question

Эта проблема может быть решена путем создания BST из заданного массива целых чисел. Вставка в BST принимает O (logn). Таким образом, n вставок будет принимать O (nlogn). И тогда самая длинная подпоследовательность может быть получена путем перемещения только самых правых детей, начиная с корня. Это может привести к максимальному O9n). Таким образом, общая временная сложность будет O (nlogn). Правильно ли это?

Answer 1

Нет, этот подход неверен. Рассмотрим это дерево:

10 
    2 11 
1 3 
    4 

Очевидно, что самый длинный увеличение подпоследовательности здесь 2,3,4 но ваш алгоритм даст 10,11, который короче.

В то же время невозможно объяснить, как было построено мое дерево. Обе эти последовательности дадут одно и то же дерево:

10,2,1,3,4,11 
10,11,2,1,3,4 

Эти два варианта имеют разные длинные возрастающие подпоследовательности!