ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > 103. Динамическое программирование > задача:


Наибольшая возрастающая подпоследовательность

Задачи раздела

• Ежевика
• Жадина
• Игра с разрезанием
• Количество путей
• Макс и K-равные числа HARD
• Макс и Дом интернета
• Макс и бельевая верёвка
• Макс и перестановка цифр
• Наибольшая возрастающая по...
• Наибольшая общая подпоследова...
• Непрерывный рюкзак
• Несчастливые дни
• Подотрезок с максимальной суммой
• Распределение студентов
• Странная функция
• Экзаменационные билеты
• Экспериментальный отбор

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Наибольшая возрастающая подпоследовательность
Наибольшая возрастающая подпоследовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив A, элементами которого являются целые числа.

Найдите длину максимальной подпоследовательности его элементов (не обязательно непрерывной), в которой каждое следующее число строго больше предыдущего.

Входные данные

Первая строка содержит целое число N (1 ≤ N ≤ 1000) — количество элементов массива.

Вторая строка содержит N целых чисел Ai ( - 104 ≤ Ai ≤ 104) — элементы массива.

Выходные данные

Выведите одно целое число — длину наибольшей возрастающей подпоследовательности рассматриваемого массива.

Примеры

Входные данные
10
-5 3 2 3 -6 2 8 1 10 4
Выходные данные
5
Входные данные
5
1 2 3 4 5
Выходные данные
5
Входные данные
8
7 -9 -5 5 -6 4 -2 10
Выходные данные
4
Для отправки решений необходимо выполнить вход.

www.contester.ru