一、问题：a[]={2,1,5,3,6,4,8,9,7}最长是5(1,3,4,8,9)二、问题分析：dp数组设一维，因为只有一个数组。dp数组存的是前j项最大递增子序列的个数。如果当前比前面的数大，那就前面的个数+1。（前面的意思是，当前这个数前面所有。）三、状态转移方程：
dp[i]=max(dp[i],dp[j]+1)
其中：i是当前数字，j是从0开始到i处。四、代码
#include<stdio.h>#definemax(x,y)(x)>(y)?(x):(y)inta[]={2,1,5,3,6,4,8,9,7};intn=sizeof(a)/sizeof(a[0]);intdp[101];intres=0;//答案voidsolve(){for(inti=0;i<n;i++){dp[i]=1;//单个数，自己递增，所以初始化为1for(intj=0;j<i;j++){if(a[i]>a[j])//如果比前面的大dp[i]=max(dp[i],dp[j]+1);//当前的个数和之前个数+1求最大值res=max(res,dp[i]);}}printf("%d\n",res);}intmain(){solve();return0;}
