这题目是经典的DP题目，也可叫作LIS（Longest Increasing Subsequence）最长上升子序列 或者 最长不下降子序列。很基础的题目，有两种算法，复杂度分别为O(n*logn)和O(n^2) 。

利用LCS算法实现

思路：设原序列为A[],将A[]进行排序后生成排好序的序列B[]，利用LCS 算法查找A[],B[]的最长公共子序列即可找出LIC。
时间复杂度：分为排序和LCS两块，最终为O(n^2)
代码可以参考前面的关于LCS的文章。

动态规划的思想

定义L(j)={ max(L(i))+1, i<j且a[i]<a[j] }。也就是说，我们需要遍历在j之前的所有位置i(从0到j-1)，找出满足条件a[i]<a[j]的L(i)，求出max(L(i))+1即为L(j)的值。最后，我们遍历所有的L(j)（从0到N-1），找出最大值即为最大递增子序列。时间复杂度为O(N^2)。

代码实现：

#include 
     
       #define SIZE 10000 #include 
      
        #include 
       
         using namespace std; //a[]为序列数组，d[t]记录0...t的LIS的最大长度，p[]记录前一个LIS的位置 void LIS(int *a,int length,int *d,int* p) {     int i,j;     d[0]=1;p[0]=-1;             //初始化，以a[0]结尾的最长递增子序列长度为1     for(i=1;i
        
         a[j]&&d[j]+1>d[i])             {                 d[i]=d[j]+1;                 p[i]=j;            //记录位置             }     } } void printAnswer(int *d,int* p,int length) {     int i,j,max=0;     for(i=0;i
         
          max)         {             max=d[i];             j=i;         }     }     cout<<"Max length:"<
          
           <
vec; for(i=0;i