Поиск самой длинной возрастающей подпоследовательности
Дан массив из
n целых чисел. Требуется найти в этом массиве самую длинную возрастающую подпоследовательность. Если существует несколько таких подпоследовательностей, вы можете вывести любую из них.Подпоследовательность массива получается путём удаления некоторых (возможно, ни одного) элементов исходного массива без изменения порядка оставшихся элементов. Например, если массив задан как , тогда является подпоследовательностью , а — нет, так как порядок элементов не сохраняется.
💡
Возрастающая подпоследовательность массива — это подпоследовательность, в которой элементы идут в порядке возрастания. Например, если массив задан как , тогда будет возрастающей подпоследовательностью , а вот не будет, потому что элементы не идут по возрастанию.
Входные данные
В первой строке входных данных содержится одно целое число
n (1 ≤ n ≤ 100 000), обозначающее длину массива.Во второй строке находятся
n целых чисел, записанных через пробел (), которые являются элементами массива.Выходные данные
В первой строке необходимо вывести одно целое число
k — длину самой длинной возрастающей подпоследовательности массива.Во второй строке следует вывести
k чисел, записанных через пробел, которые образуют эту подпоследовательность. Если существует несколько корректных вариантов, можно вывести любой из них.Примеры
Входные данные | Выходные данные |
8
1 3 2 4 5 2 6 5 | 5
1 2 4 5 6 |
6
10 9 2 5 3 7 | 3
2 5 7 |
Примечание
Во втором примере подпоследовательность также является допустимой возрастающей подпоследовательностью длины 3.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB