最长递增子序列

题目描述

求一个数列中，递增的最长的子序列（不要求连续）的长度。

输入描述

第一行输入一个整数n（n<1000)。 第二行输入n个整数（每个整数小于1000）组成的一个数列，相互之间用空格隔开。

输出描述

输出所求的结果。

输入样例

10 4 2 9 4 9 6 7 2 9 6

输出样例

5

提示

AC代码如下：

#include<stdio.h> #include<stdlib.h> #include<string.h> int ai[1001]; int dp[1001]; int mmax=0; int num=0; int main() { int n,i,j; memset(dp,0,sizeof(dp)); scanf("%d",&n); for( i=1;i<=n;i++) scanf("%d",&ai[i]); for(i=1;i<=n;i++) { dp[i]=1; for(j=1;j<i;j++) { if(ai[i]>ai[j]&&dp[i]<dp[j]+1) { dp[i]=dp[j]+1; } } if(dp[i]>dp[mmax]) { mmax=i; } } printf("%d\n",dp[mmax]); }