最长递增子序列问题的求解（LIS）

最长递增子序列问题的求解

 

最长递增子序列问题是一个很基本、较常见的小问题，但这个问题的求解方法却并不那么显 而易见，需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想，能够锻炼设计较复杂算法的思 维，我对这个问题进行了较深入的分析思考，得出了几种复杂度不同算法，并给出了分析和证明。

一，    最长递增子序列问题的描述

设L=<a₁,a₂,…,a_n>是n个 不同的实数的序列，L的递增子序列是这样一个子序列Lin=<a_K1,a_k2,…,a_km>，其中k₁2<…m且a_K1k2<…km。求最大的m值。

二，    第一种算法：转化为LCS 问题求解

设序列X=<b₁,b₂,…,b_n>是对序列L=<a₁,a₂,…,a_n>按递增排好序的序列。那么显然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。

最长公共子序列问题用动态规划的算法可解。 设Li=< a₁,a₂,…,a_i>,Xj=< b₁,b₂,…,b_j>，它们分别为L和X的子序列。令C[i,j]为Li与Xj的最长公共子序列的长 度。则有如下的递推方程：

这可以用时间复杂度为O(n²)的算法求解，由于这个算法上课时讲过，所以具体代码在此略去。求最长递增子序列的算法时间复杂度由排序所用的O(nlogn)的时 间加上求LCS的O(n²)的时 间，算法的最坏时间复杂度为O(nlogn)＋O(n²)＝O(n²)。

三，    第二种算法：动态规划法

设f(i) 表示L中以a_i为末元素的最长递增子序列的长度。则有如下的递推 方程：

这个递推方程的意思是，在求以a_i为末元素的最长递增子序列时，找到所有序号在L前面且小于a_i的元素a_j，即ja_ji。如果这样的元素存在，那么对所有a_j,都有一个以a_j为末元素的最长递增子序列的长度f(j)，把其中最大的 f(j)选出来，那么f(i)就等于最大的f(j)加上1，即以a_i为末元素的最长递增子序列，等于以使f(j)最大的那个a_j为末元素的递增子序列最末再加上a_i；如果这样的元素不存在，那么a_i自身构成一个长度为1的以a_i为末元素的递增子序列。

这个算法由Java实现的代码如下：

public void lis(float[] L)

  {

         int n = L.length;

         int[] f = new int[n];//用于存 放f(i)值；

         f[0]=1;//以第a₁为末元素的最长递增子序列长度为1；

         for(int i = 1;i循 环n-1次

         {

                f[i]=1;//f[i]的最小值为1；

                for(int j=0;j循 环i 次

                {

                       if(L[j]f[i]-1)

                              f[i]=f[j]+1;//更新f[i]的值。

                }

         }

         System.out.println(f[n-1]);            

              }

这个算法有两层循环，外层循环次数为n-1次，内层循环次数为i次，算法的时间复杂度

所以T(n)=O(n²)。这 个算法的最坏时间复杂度与第一种算法的阶是相同的。但这个算法没有排序的时间，所以时间复杂度要优于第一种算法。

四，    对第二种算法的改进

在第二 种算法中，在计算每一个f(i)时，都要找出最大的f(j)(ja_ji最大的f(j)，如果能将让f(j)有序，就可以使用二分查找，这样算法的时间复杂度就可能降到O(nlogn)。于是想到用一个数组 B来存储“子序列的”最大递增子序列的最末元素，即有

B[f(j)] = a_j

在计算f(i)时，在数组B中用二分查找法找到满足ja_ji的最大的j,并将B[f[j]+1]置为a_i。下面先写出代码，再证明算法的证明性。用Java实现的代码如下：

lis1(float[] L)

{

    int n = L.length;

    float[] B = new float[n+1];//数组B；

    B[0]=-10000;//把B[0]设为最小，假设任何输入都大于 -10000；

    B[1]=L[0];//初始时，最大递增子序列长度为1的最末元素为a₁

    int Len = 1;//Len为当前最大递增子序列长度，初始化为1；

    int p,r,m;//p,r,m分别为二分查找的上界，下界和中点；

    for(int i = 1;i

    {

        p=0;r=Len;

        while(p<=r)//二分查找最末元素小于a_i+1的长度最大的最大递增子序列；

        {

           m = (p+r)/2;

           if(B[m]

           else r = m-1;

        }

        B[p] = L[i];//将长度为p的最大递增子序列的当前最末元素置为a_i+1;

        if(p>Len) Len++;//更新当前最大递增子序列长度；

       

       

    }

    System.out.println(Len);

}

 

现在来证明这个算法 为什么是正确的。要使算法正确只须证如下命题：

命题1：每一次循环结束数组B中元素总是按递增顺序排列的。

证明：用 数学归纳法，对循环次数ｉ进行归纳。

当i=0时，即程序还没进入循环时，命题显然 成立。

设i时命题成立，当i=k时，假设存在j11]>B[j₂]，因为第i次 循环之前数组B是递增的，因此第i次循环时B[j₁]或B[j₂]必有一个 更新，假设B[j₁]被更新为元 素a_i+1，由于a_i+1=B[j₁]> B[j₂]，按算法a_i+1应更新B[j₂]才对，因此产生矛盾；假设B[j₂]被更新，设更新前的元素为s,更新后的元 素为a_i+1，则由算法可 知第i次循环前有B[j₂]＝s< a_i+1< B[j₁]，这与归纳假设矛盾。命题得证。

命题2：B[c]中存储的元素是当前所有最长递增子序列长度为c的 序列中，最小的最末元素，即设当前循环次数为i，有B[c]={a_j| f(k)=f(j)=c∧k,j≤i+1→a_j≤a_k}(f(i)为与 第二种算法中的f(i)含义相同)。

证明：程 序中每次用元素a_i更新B[c]时(c=f(i))，设B[c]原来的值为s，则必有a_i，不然a_i就能接在s的后面形成长度为c+1的最长递增子序列，而更新B[c+1]而不是B[c]了。所有B[c]中存放的总是当前长度为 ｃ的最长递增子序列中，最小的最末元素。

命题3：设第i次循环后得到的p为p(i+1)，那么p(i)为以元素a_i为最 末元素的最长递增子序列的长度。

证明：只 须证p(i)等于第二种算法中的f(i)。显然一定有p(i)<＝f(i)。假设p(i)，那么有两种情况，第一种情况是由二分查找法找到的p(i)不是数组B中 能让a_i接在后面成为新的 最长递增子序列的最大的元素，由命题1和二分查找的方法可知，这是不 可能的；第二种情况是能让a_i接在后面形成长 于p(i)的最长递增子序列的元素不在数组B中，由命题2可 知，这是不可能的，因为B[c]中存放的是最末元素最小的长度为c的最长递增子序列的最末元素，若a_i能接在长度为L(L> p(i))的最长递增子序列后面，就应该能接在B[L]后面，那么就应该有p(i)=L,与L> p(i)矛盾。因此一定有p(i)＝f(i)，命 题得证。

算法的循环次数为n，每次循环二 分查找用时logn，所以算法的时间复杂度为O(nlogn)。这个算法在第二种算法的基础上得到了较好的改进。