求数组中最长递增子序列的长度

浅浅的花香味﹌ 2021-12-04 06:05 276阅读 0赞

求数组中最长递增子序列的长度

什么是最长递增子序列呢?  
问题描述如下:  
   设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。

如：在序列1，-1，2，-3，4，-5，6，-7中，其最长的递增子序列为1，2，4，6。其长度为4。  
对于这个问题有以下几种解决思路:  
   1、把a1,a2,...,an排序，假设得到a'1,a'2,...,a'n，然后求a的a'的最长公共子串，这样总的时间复杂度为o(nlg(n))+o(n^2)=o(n^2);  
   2、动态规划的思路：  
    另设一辅助数组b,定义b\[n\]表示以a\[n\]结尾的最长递增子序列的长度，则状态转移方程如下：b\[k\]=max(max(b\[j\]|a\[j\]<a\[k\],j<k)+1,1);  
    这个状态转移方程解释如下：在a\[k\]前面找到满足a\[j\]<a\[k\]的最大b\[j\],然后把a\[k\]接在它的后面，可得到a\[k\]的最长递增子序列的长度，或者a\[k\]前面没有比它小的a\[j\]，那么这时a\[k\]自成一序列，长度为1.最后整个数列的最长递增子序列即为max(b\[k\]   | 0<=k<=n-1);  
    实现代码如下：

#include <iostream>
    using namespace std;
    int main()
    {
           int i,j,n,a[100],b[100],max;
           while(cin>>n)
           {
                  for(i=0;i<n;i++)
                         cin>>a[i];
                  b[0]=1;//初始化，以a[0]结尾的最长递增子序列长度为1
                  for(i=1;i<n;i++)
                  {
                         b[i]=1;//b[i]最小值为1
                         for(j=0;j<i;j++)
                                if(a[i]>a[j]&&b[j]+1>b[i])
                                       b[i]=b[j]+1;
                  }
                  for(max=i=0;i<n;i++)//求出整个数列的最长递增子序列的长度
                         if(b[i]>max)
                                max=b[i];
                  cout<<max<<endl;
           }
           return 0;
    }

显然，这种方法的时间复杂度仍为o(n^2);

3、对第二种思路的改进：  
    第二种思路在状态转移时的复杂度为o(n),即在找a\[k\]前面满足a\[j\]<a\[k\]的最大b\[j\]时采用的是顺序查找的方法，复杂度为o(n).  
    设想如果能把顺序查找改为折半查找，则状态转移时的复杂度为o(lg(n)),这个问题的总的复杂度就可以降到nlg(n).

转载于:https://www.cnblogs.com/Xilian/p/3647540.html