输入两行，一行是整数n，0<n<20000。第2行是由空格分开的n个整数。

输出一行，一个整数，表示“最长递增子序列”的长度m。

测试案例：
输入：

9
5 6 1 2 9 3 4 7 8

输出：

6

（解释：输入数据对应测最长递增子序列是“1 2 3 4 7 8”，长度为6）

---

首先来分析题意。

根据解释我们可以知道，“最长递增子序列”不一定是连续的，只要选取的几个元素按照顺序出现且递增。即“选取最多的数，根据出现顺序排列时递增”。枚举所有递增子序列并且求最长的做法肯定会超时的，所以我们得想想办法。

注意这个数列，1 3 4 2 6。为了方便，对于数列中的某一个数，我把以它为结尾的数列写在下面。

数	1	3	4	2	6
数列	1	1-3	1-3-4	1-2	1-3-4-6
数列长度	1	2	3	2	4

出现了两个长度为2的数列。这一点很有趣，它提醒我们，递增子序列长度和序列内部的数具体是多少没有关系，决定一个递增子序列只看最大的那个数的值，以及内部出现了多少个数。

于是这张表可以写作

数	1	3	4	2	6
以这个数结尾的 最长递增子序列 的长度	1	2	3	2	4

因为后加上去的数肯定不会出现在“以前面数结尾的 最长递增子序列”中，所以我们可以从头开始，每次加上一个数，并找到目标子序列的长度将其存下来。比方说在`后面加上一个5`。

1	3	4	2	6	5
1	2	3	2	4	?

怎么求出这个位置对应的长度呢？

刚开始，最长的序列为5，长度为1；

5>1，目前最长的序列为1-5，长度为2；

5>3，目前最长的序列是1-3-5，长度为3。

你可以理解成5“继承”了以3为结尾的序列，像玩蜘蛛纸牌的时候把A234连到5上。

同理5>4，数列变成1-3-4-5，长度为4。

这时候5>2，但如果5继承以2为结尾的数列，就变成1-2-5，而当前的最优结果1-3-4-5相较于它而言更好，所以保留。

最后5<6，没法继承以6为结尾的数列。

分析结束，我们就此知道，以5为结尾的最长递增子序列长度为4。

总结下来就是

我比你大：如果继承的序列长度大于已有的序列，则继承，反之不继承。

我比你小：继承不了，忽略。

从第一个数开始，每次加一个数并计算“以它结尾的最长递增子序列”的长度，最后找到所有数对应序列长度最大的那个就行了。

用代码实现可以这样写：

for(int i=0;i<n;i++)
{
	b[i]=1;
	for(int j=0;j<i;j++)
	{
		if(a[i]>a[j]) b[i]=max(b[i],b[j]+1);
        // +1是因为继承序列时需要把自己也算进去
	}
}
// n为原数列的长度，a[]中存储各个数的值，b[]中存储长度。

核心部分搞定，剩下的就是输入输出了。输入可以读一个算一个，也可以存起来一起算，输出同理。我的代码实现如下，习惯不是很好。

#include<bits/stdc++.h>
using namespace std;
int a[20010],b[20010];
int main()
{
    //输入
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	
    //处理
	if(n==1)
	{
		cout<<1<<endl;
		return 0;
	}
	
	for(int i=0;i<n;i++)
	{
		b[i]=1;
		for(int j=0;j<i;j++)
		{
			if(a[i]>a[j]) b[i]=max(b[i],b[j]+1);
		}
	}
	
    //输出
	int ans=0;
	for(int i=0;i<n;i++) ans=max(ans,b[i]);
	cout<<ans<<endl;
	return 0;
}