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