3622
правки
Изменения
→Решение за O(N log N): исправлена бага в алгоритме за O(n log n)
{{Задача
|definition =
Дан массив из <tex>n</tex> чисел: <tex>a[0..n - 1]</tex>. Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.
}}
{{Определение
|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 leqslant i_j \le leqslant n </tex> и , причем <tex> k </tex> {{--- }} наибольшее из возможных.
}}