Изменения
Нет описания правки
{{Определение
|definition =
'''Наибольшая возрастающая подпоследовательность ''' (''англ''. Longest increasing subsequence - LIS) строки <tex> x </tex> длины <tex> n </tex> - это последовательность <tex> x[i_1] < x[i_2] < \dots < x[i_k] </tex> символов строки <tex> x </tex> таких, что <tex> i_1 < i_2 < \dots < i_k, 1 \le i_j \le n </tex> и <tex> k </tex> - наибольшее из возможных.
}}
Задача заключается в том, чтобы отыскать это наибольшее <tex> k </tex> и саму подпоследовательность.
Известно несколько алгоритмов решения этой задачи.
==== Пример алгоритма, работающего за время <tex> O(n^2) </tex> ====
