现在的位置: 首页 > 综合 > 正文

算法:最长递增子序列!

2017年10月27日 ⁄ 综合 ⁄ 共 2290字 ⁄ 字号 评论关闭

俗称the Longest Increase Subsequence,or LIS

查了好多博客都写的 太!简!略!,或者要不然 我的水平太!垃!圾!

现在我就来记录一下学这个DP案例时的思路历程!。

= =目前已经搞定了,下面哪里讲的不好请留言。

给定一个数字串A=a1...an(或字符串,只要能比大小的串即可);

问题是如何求出这个串A的最长递增子序列C呢?

1、先分析“最长递增子序列”这个词语,

            A的子序列的定义是:A删除某些元素剩下的串。[也就是C不一定是A中某一段连续的元素串,但C中各个元素在A中的先后顺序一定不能改变。]

2、在来分析一下这个问题,求最长的递增子序列,那就有:

             方法1:暴力穷举,举出所有递增子序列(从所有2^n个子序列中找出递增的),再找出最长的就ok了。O(2^n) ×,太慢。

             方法2:枚举,把上面的穷举结果分类,所有递增子序列的结尾元素无非只有n个可能[a1/a2/.../an]。

    【并且有个暂时没什么用的规律:假如某个递增序列的结尾是ai,那序列中的元素必定只有ai前面的元素(否则它不是A的子序列);换个说法,结尾是ai的递增子序列,与ai之后的元素没有关系(只与其前面的元素有关),这可以用以确定DP的方向。】

ok,那我们几乎已经达到出口了。

再对刚刚方法2加个约束,我们只要找出n个递增子序列: 分别是以ai(i=1...n)结尾的最长递增子序列(先是n个子序列集合{以ai结尾的递增子序列},再从n个集合中找出最长的)。A的LIS无非是这n个子序列中最长的那个。

问题来了,如何求这n个最长递增子序列呢?

再来分析一下,实际上,这n个最长递增子序列之间有某种关系。

【实际上,上面的某种关系就是:以位于较后元素结尾的递增子序列是在位于较前元素结尾的递增子序列基础上生成的,分别加上“最长”修饰】

假如以ax(x=1...i)结尾的i个最长递增子序列已经求得,分别是:

       以ax结尾的最长递增子序列   

1:a1                                              

2:a1a2(这里假设a2 > a1)   

3:...

...

i:xxxxxai                                      

考虑以a(i+1)结尾的最长递增子序列,应该是这样的:

the Longest of

{ XXXXaj,ai+1 |  if ai+1 > aj(j = 1 to i)}

or ai+1                if ai+1 < ALL ai

设c[i]表示以ai结尾的最长递增子序列,则有

           |      a1             if i=1

c[i] =  |       ai                if i > 1 && ALL aj,j=1..i-1 > a[i]

          |       Longest { <c[j],ai>(if i > 1 && aj < ai), j=1,2,...,i-1} 

也就是要求c[i],必须先求出所有c[j],j<i,并遍历一遍它们。==> DP(自底向上):O(1+2+...+n)=n*(n+1)/2)=O(n^2)

很容易根据上面这个式子写出DP算法或者递归算法(Memo),其时间复杂度O(n^2)

上面DP算法求c[i],or以某个元素a[i]结尾的LIS时,需要之前的c[j],j<i都被求出,并且需要遍历一遍所有的c[j],j<i。

                   有没有更好的方法呢?有的!!!

                   方法3:在线算法,以另一种规律求解。

这种想法提出的是从另一个角度考虑问题,

1、串的IS的长度无非是        【1,2,...,LEN】LEN为LIS的长度。

2、每个长度的IS的结尾元素【{..},{..},... ,  {..}】各自都是一个集合

3、找出每个集合最小的        【x,y,...,z】*

考虑*: ①:  【x,y,...,z】从左到右是递增的(或不减,看具体条件是否允许相等)。 

证明:反证法:假设长度为i的IS其最小结尾元素是m,长度为j的IS其最小结尾元素是m',其中i<j,并且有m > m';可以把长度为j的并且结尾为m'的IS去掉m'前面的j-i个元素,组成一个长度为i的IS,可以得到结尾为m',说明m不是最小的,矛盾;假如要求的序列是严格递增的,那么也不可能出现相等的情况,只能从左到右也是严格递增,证法同前。

因此就有了一个算法:根据当前处理的输入串(Arr),动态维护一个数组D[],D[i]保存的是当前输入串的情况下,长度为i的IS的最小结尾元素,自然这个数组的最后一个元素D[LEN]保存的就是当前串的LIS的最小结尾元素。

为什么用“当前串”的说法,从左到右扫描Arr,每读取一个元素就更新D[],(更新当前数组的值或将数组扩大即LEN++)。具体如下:

i = 2,LEN = 1;

D[LEN] = A[i - 1];//第一个元素,这里为初始化

while(d = Arr[i]){

  if(d > D[LEN]){

     D[++LEN] = d;

  }

 else{

       j=LEN;

        while(j>0)do

        {

          if( d > D[j])

                break;

         j--;

       }

       D[j+1] = d;

 }

 i++;

}

不过上面的算法还是O(n^2)原因是中间还是用了遍历,由于*的存在,这个算法得以是正确的,并且由于*我们可以用效率更高的二分查找,查找当前输入可以更新的是D[]中的哪一个。优化后是O(nlgn)。

PS:我说的太多了。。。可以简略地看。。。。

抱歉!评论已关闭.