单调递增最长子序列

7-1 单调递增最长子序列 (20 分)

设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

输入格式:

输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开

输出格式:

最长单调递增子序列的长度

输入样例:

在这里给出一组输入。例如：

51 3 5 2 9

结尾无空行

输出样例:

在这里给出相应的输出。例如：

4

结尾无空行

#include<iostream>

using namespace std;

int num[10000];

int len[10000];

const int a = 1e9;

int main()

{

int n;

cin >> n;

for (int i = 1;i <= n;i++)

{

cin >> num[i];

}

num[0] = 0;

len[0] = 0;

for (int i = 1;i <= n;i++)

{

len[i] = 0;

for (int j = 0;j < i;j++)

{

if (num[i] > num[j])

{

len[i] = max(len[i],len[j] + 1);//len[i] = max {len[j] + 1 | num[i] > num[j]} 0 <= j < i//这种方法可以，但还要经过下面的排序选出最大值

}

}

}

int ans=0;

for(int i=1;i<=n;i++)

ans=max(ans,len[i]);

cout<<ans;

return 0;

}