Наибольшая возрастающая подпоследовательность 1
Пусть у нас есть массив из
n целых чисел. Требуется найти в этом массиве самую длинную (наибольшую) возрастающую подпоследовательность. Если существует несколько таких подпоследовательностей, вы можете вывести любую из них.Подпоследовательность массива получается, если из исходного массива удалить некоторые (возможно, ни одного) элементы, не меняя при этом порядок оставшихся. Например, если дан массив , то является подпоследовательностью массива , а вот не является подпоследовательностью , поскольку в ней нарушён исходный порядок элементов.
💡
Возрастающая подпоследовательность массива — это подпоследовательность, в которой элементы идут в порядке возрастания. Например, если дан массив , то является возрастающей подпоследовательностью , а вот — нет, так как элементы не расположены по возрастанию.
Входные данные
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ 1000), задающее длину массива.Вторая строка содержит
n целых чисел, разделённых пробелами: (), которые представляют элементы массива.Выходные данные
Программа должна вывести длину наибольшей возрастающей подпоследовательности массива.
Примеры
Входные данные | Выходные данные |
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