最长递增子序列（只求大小）模板-白红宇

最长递增子序列（只求大小）模板

阅读量：5981 次

发布时间：2019-06-20

本文共 1326 字，大约阅读时间需要 4 分钟。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define maxn 40005int main(){    int a[8] = {
   5,4,6,8,7,10,3,6};    int f[10];    f[0] = 1;    int ans = 0;    for(int i=1;i<8;i++){        f[i] = 1;        for(int j=0;j
         
          f[i]-1){
   //之所以是大于f[i]-1是因为要保证现在的递增子序列是最长的                 f[i] = f[j] + 1;//加一加的是本身这个数             }        }        ans = max(ans,f[i]);//ans求的是最长的长度，最后一个不一定是最长的     }    cout << ans << endl;    return 0;}

用二分法加快了查找符合条件的数构成递增子序列的过程

#include 
     
      #include
      
       #include
       
        #include
        
         using namespace std;int main(){    int a[8] = {
   5,4,6,8,7,10,3,6};    int B[9];     B[0]=-10000;//把B[0]设为最小，假设任何输入都大于-10000；    B[1]=a[0];//初始时，最大递增子序列长度为1的最末元素为a1    int Len = 1;//Len为当前最大递增子序列长度，初始化为1；    int p,r,m;//p,r,m分别为二分查找的上界，下界和中点；    for(int i = 1;i<8;i++)    {        p=0;r=Len;        while(p<=r)//二分查找最末元素小于ai+1的长度最大的最大递增子序列；        {           m = (p+r)/2;           if(B[m]
         
          Len) Len++;//更新当前最大递增子序列长度；    }    cout << Len << endl;    return 0;}