Задача о наибольшей возрастающей подпоследовательности

Определение:

Наибольшая возрастающая подпоследовательность (англ. Longest increasing subsequence - LIS) строки [math] x [/math] длины [math] n [/math] - это последовательность [math] x[i_1] \lt x[i_2] \lt \dots \lt x[i_k] [/math] символов строки [math] x [/math] таких, что [math] i_1 \lt i_2 \lt \dots \lt i_k, 1 \le i_j \le n [/math] и [math] k [/math] - наибольшее из возможных.

Задача заключается в том, чтобы отыскать это наибольшее [math] k [/math] и саму подпоследовательность. Известно несколько алгоритмов решения этой задачи.

Пример алгоритма, работающего за время [math] O(n^2) [/math]

Строим таблицу [math] A[1 \dots n]. Каждый её элемент \lt tex\gt A[i] [/math] - длина наибольшей возрастающей подпоследовательности, оканчивающейся точно в позиции [math] i [/math]. Если мы построим эту таблицу, то ответ к задаче - наибольшее число из этой таблицы. Само построение тоже элементарно: ,[math] A[i] = \max{i-1}_{j = 1} {(A[j] + 1)} [/math], для которых [math] x[j] \lt x[i] [/math]. База динамики [math] A[1] = 1 [/math].