Изменения
Нет описания правки
==== Пример алгоритма, работающего за время <tex> O(n^2) </tex> ====
Строим таблицу <tex> A[1 \dots n]. Каждый её элемент <tex> A[i] </tex> - длина наибольшей возрастающей подпоследовательности, оканчивающейся точно в позиции <tex> i </tex>. Если мы построим эту таблицу, то ответ к задаче - наибольшее число из этой таблицы.
Само построение тоже элементарно: ,<tex> A[i] = \max {i-1}_{j = 1} {(A[j] + 1) } </tex> , среди всех для которых <tex> x[j ] < x[i, для которых Mj ] < Mi/tex>. Перый элемент A1 = 1, что очевидно. База динамики <tex> \max^{n}_{iA[1] =1} {T^{\mu}}_{\nu,\;i} </tex>.
