Некоторые методы решения задачи о наибольшей возрастающей подпоследовательности:

• Алгоритм, работающий за O(n log n). 12 Для строки x хранятся массивы M и P длины n. 1 M[i] содержит индекс наименьшего по величине из последних элементов возрастающих подпоследовательностей длины i, а P[i] — индекс предшествующего символа для наидлиннейшей возрастающей подпоследовательности, оканчивающейся в i-й позиции. 2 На каждом шаге происходит переход к следующему элементу строки, для каждого перехода требуется не более логарифма времени (бинарный поиск по массиву M). 2
• Использование деревьев ван Эмде Боаса. 1 В частном случае, если строка является перестановкой 1..n, задача имеет решение за n log log n с использованием деревьев ван Эмде Боаса. 1
• Сведение задачи к поиску длиннейшего пути в ориентированном ациклическом графе. 1 Ребра задаются между возрастающими элементами. 1 Подсчёт длиннейшего пути занимает линейное время от числа рёбер, но в худшем случае оно может быть квадратично от длины строки. 1
• Использование табло Юнга. 3 Решение позволяет найти длину наибольшей возрастающей подпоследовательности, но без возможности её восстановления. 3 Длина первой строки табло и будет искомой величиной. 3