#1348. 最长上升子序列Ⅰ

最长上升子序列Ⅰ

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一个数的序列bi\red{b_i},当b1<b2<...<bS\red{b_1 < b_2 < ... < b_S}的时候,我们称这个序列是上升的。

对于给定的一个序列(a1,a2,...,aN\red{a_1, a_2, ..., a_N}),我们可以得到一些上升的子序列(ai1,ai2,...,aiK\red{a_{i1}, a_{i2}, ..., a_{iK} }),这里1<=i1<i2<...<iK<=N\red{1 <= i_1 < i_2 < ... < i_K <= N}。比如,对于序列(1\red{1}, 7\red{7}, 3\red{3}, 5\red{5}, 9\red{9}, 4\red{4}, 8\red{8}),有它的一些上升子序列,如(1\red{1}, 7\red{7}), (3\red{3}, 4\red{4}, 8\red{8})等等。

这些子序列中最长的长度是4,比如子序列(1\red{1}, 3\red{3}, 5\red{5}, 8\red{8}).

你的任务,就是对于给定的序列,求出最长上升子序列的长度。

输入样例

输入的第一行是序列的长度N\red{N} (1<=N<=1000\red{1 <= N <= 1000})。第二行给出序列中的N个整数,这些整数的取值范围都在0\red{0}104\red{10^4}

输出样例

最长上升子序列的长度。

输入样例

7
1 7 3 5 9 4 8

输出样例

4

少年宫周五高级班期末测试

未参加
状态
已结束
规则
IOI
题目
5
开始于
2023-6-2 17:30
结束于
2023-6-2 20:30
持续时间
3 小时
主持人
参赛人数
17