设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。
输入格式:
输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开
输出格式:
最长单调递增子序列的长度
输入样例:
在这里给出一组输入。例如：
5 1 3 5 2 9
输出样例:
在这里给出相应的输出。例如：
4
代码：
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int i,j,n,maxlen;
cin>>n;
int dp[n],num[n]; // dp[i]表示以第i个数字为结尾的最长子序列长度
for(i=1;i<=n;i++)
{
cin>>num[i];
dp[i]=1; //初始化
}
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++) //遍历所有a[i]前的元素
{
if(num[j]<num[i])
dp[i]=max(dp[i],dp[j]+1); // 把i接到 以j为结尾的单调递增子序列 的后面
}
maxlen=max(maxlen,dp[i]); // 更新最长单调递增子序列长度
}
cout<<maxlen;
return 0;
}