问题描述：输入规模n和由n个元素组成的序列A1...An，求序列中的最长单调递增子序列的长度。

解题思路：这是一个求最优解的题目，可以采用动态规划的方法。首先，找出原始问题的最优子结构。假设序列A1...Ai-1(iAk，则A1...Ai中最长递增子序列长度为A1...Ai-1中最长子序列长度加1，否则和A1...Ai-1中最长递增子序列长度相同。如此可以得到一个递归式：设数组L1...Ln存诸子序列A1...A1，A1...A2,A1...A3,A1...An中最长递增子序列的长度，则可以得到一个递归式：

          [1                                i=1;   L[i]=[MAX(L[1]...L[i-1])        1          [MAX(L[1]...L[i-1])+1    1Ak

根据上式构造最优结构即最长公共子序列，代码如下：

#include #define MAXSIZE 10000int LstSub(int A[],int n){ int L[MAXSIZE],i,j,k,max; L[0]=1; for(i=1;i {  max=0X80000000;  for(j=0;j  {   if(L[j]>max)   {  max=L[j]; k=j;  }  }  if(A[i]>A[k])   L[i]=max+1;  else   L[i]=max; } return L[n-1];}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        int A[MAXSIZE],i,lst;        for(i=0;i            scanf("%d",A+i);        lst=LstSub(A,n);        printf("%d/n",lst);    }    return 0;}