题目描述

设有由 $n$ 个 (可能有相同) 的整数组成的数列，记为: {$a_1$、$a_2$、...、$a_n$}。

例如 {3，18，7，14，10，12，23，41，16，24}。若存在 $i_1 \lt i_2 \lt i_3 \lt \dots \lt i_e$ 且有 $a_{i_1} \lt a_{i_2} \lt ... \lt a_{i_e}$ 则称为长度为 $e$ 的上升子序列。

如上例中 {3，18，23，24} 就是一个长度为 $4$ 的上升序列，同时也是 {3，7，10，12，16，24} 长度为 $6$ 的上升子序列。

程序要求，当原数列给出之后，求出最长的上升子序列的长度。

输入格式

第一行为 $n$，表示 $n$ 个数（$10 \le n \le 10000$）

第二行 $n$ 个整数，数值之间用一个空格分隔（$1 \le a_i \le n$）

输出格式

一个整数，代表最长上升子序列的长度。

数据样例

3
1 2 3

3

7
1 3 7 7 11 8 10

5

完善程序

#include<bits/stdc++.h>
using namespace std;
int n,a[1001],len[1001],ans;
int main()
{
	scanf("%d",&n);
	int MAX;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		
	for(int i=1;i<=n;i++)
	{
		MAX = 填空(1);
		for(int j=1; 填空(2) ;j++)
		{
			if(a[j]<=a[i])
			{
				MAX = 填空(3);
			}
		}

		len[i] =  填空(4);

		ans = max(ans, 填空(5));
	}

	printf("%d",ans);
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}