Описание тега lis
Задача самой длинной возрастающей подпоследовательности состоит в том, чтобы найти подпоследовательность данной последовательности, в которой элементы подпоследовательности расположены в отсортированном порядке, от наименьшего к наибольшему, и в которой подпоследовательность является максимально длинной.
Задача самой длинной возрастающей подпоследовательности состоит в том, чтобы найти подпоследовательность данной последовательности, в которой элементы подпоследовательности расположены в отсортированном порядке, от наименьшего к наибольшему, и в которой подпоследовательность является максимально длинной. Эта подпоследовательность не обязательно является непрерывной или уникальной.
Наиболее длинные возрастающие подпоследовательности изучаются в контексте различных дисциплин, связанных с математикой, включая алгоритмику, теорию случайных матриц, теорию представлений и физику.
Задача самой длинной возрастающей подпоследовательности решается за время O(n log n), где n обозначает длину входной последовательности.