开发者社区> 嗯哼9925> 正文

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

简介:
+关注继续查看
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,能够锻炼设计较复杂算法的思维,我对这个问题进行了较深入的分析思考,得出了几种复杂度不同算法,并给出了分析和证明。
 
一,          最长递增子序列问题的描述
 
设L=<a1,a2,…,an>是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>,其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
 
二,          第一种算法:转化为LCS问题求解
 
设序列X=<b1,b2,…,bn>是对序列L=<a1,a2,…,an>按递增排好序的序列。那么显然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。
 
最长公共子序列问题用动态规划的算法可解。设Li=< a1,a2,…,ai>,Xj=< b1,b2,…,bj>,它们分别为L和X的子序列。令C[i,j]为Li与Xj的最长公共子序列的长度。这可以用时间复杂度为O(n2)的算法求解,由于这个算法上课时讲过,所以具体代码在此略去。求最长递增子序列的算法时间复杂度由排序所用的O(nlogn)的时间加上求LCS的O(n2)的时间,算法的最坏时间复杂度为O(nlogn)+O(n2)=O(n2)。
 
三,          第二种算法:动态规划法
 
设f(i)表示L中以ai为末元素的最长递增子序列的长度。则有如下的递推方程:
这个递推方程的意思是,在求以ai为末元素的最长递增子序列时,找到所有序号在L前面且小于ai的元素aj,即j<i且aj<ai。如果这样的元素存在,那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j),把其中最大的f(j)选出来,那么f(i)就等于最大的f(j)加上1,即以ai为末元素的最长递增子序列,等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai;如果这样的元素不存在,那么ai自身构成一个长度为1的以ai为末元素的递增子序列。
这个算法由Java实现的代码如下:

public void lis(float[] L)
    {
        int n = L.length;
        int[] f = new int[n];//用于存放f(i)值;
        f[0]=1;//以第a1为末元素的最长递增子序列长度为1;
        for(int i = 1;i<n;i++)//循环n-1次
        {
            f[i]=1;//f[i]的最小值为1;
            for(int j=0;j<i;j++)//循环i 次
            {
                if(L[j]<L[i]&&f[j]>f[i]-1)
                    f[i]=f[j]+1;//更新f[i]的值。
            }
        }
        System.out.println(f[n-1]);        
        }



这个算法有两层循环,外层循环次数为n-1次,内层循环次数为i次,算法的时间复杂度
所以T(n)=O(n2)。这个算法的最坏时间复杂度与第一种算法的阶是相同的。但这个算法没有排序的时间,所以时间复杂度要优于第一种算法。
 
一,          对第二种算法的改进
 
在第二种算法中,在计算每一个f(i)时,都要找出最大的f(j)(j<i)来,由于f(j)没有顺序,只能顺序查找满足aj<ai最大的f(j),如果能将让f(j)有序,就可以使用二分查找,这样算法的时间复杂度就可能降到O(nlogn)。于是想到用一个数组B来存储“子序列的”最大递增子序列的最末元素,即有
B[f(j)] = aj
在计算f(i)时,在数组B中用二分查找法找到满足j<i且B[f(j)]=aj<ai的最大的j,并将B[f[j]+1]置为ai。下面先写出代码,再证明算法的证明性。用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的最末元素为a1
        int Len = 1;//Len为当前最大递增子序列长度,初始化为1;
        int p,r,m;//p,r,m分别为二分查找的上界,下界和中点;
        for(int i = 1;i<n;i++)
        {
            p=0;r=Len;
            while(p<=r)//二分查找最末元素小于ai+1的长度最大的最大递增子序列;
            {
                m = (p+r)/2;
                if(B[m]<L[i]) p = m+1;
                else r = m-1;
            }
            B[p] = L[i];//将长度为p的最大递增子序列的当前最末元素置为ai+1;
            if(p>Len) Len++;//更新当前最大递增子序列长度;
            
            
        }
        System.out.println(Len);    
    }

 
现在来证明这个算法为什么是正确的。要使算法正确只须证如下命题:
 
命题1:每一次循环结束数组B中元素总是按递增顺序排列的。
证明:用数学归纳法,对循环次数i进行归纳。
当i=0时,即程序还没进入循环时,命题显然成立。
设i<k时命题成立,当i=k时,假设存在j1<j2,B[j1]>B[j2],因为第i次循环之前数组B是递增的,因此第i次循环时B[j1]或B[j2]必有一个更新,假设B[j1]被更新为元素ai+1,由于ai+1=B[j1]> B[j2],按算法ai+1应更新B[j2]才对,因此产生矛盾;假设B[j2]被更新,设更新前的元素为s,更新后的元素为ai+1,则由算法可知第i次循环前有B[j2]=s< ai+1< B[j1],这与归纳假设矛盾。命题得证。
 
命题2:B[c]中存储的元素是当前所有最长递增子序列长度为c的序列中,最小的最末元素,即设当前循环次数为i,有B[c]={aj| f(k)=f(j)=c∧k,j≤i+1→aj≤ak}(f(i)为与第二种算法中的f(i)含义相同)。
证明:程序中每次用元素ai更新B[c]时(c=f(i)),设B[c]原来的值为s,则必有ai<s,不然ai就能接在s的后面形成长度为c+1的最长递增子序列,而更新B[c+1]而不是B[c]了。所有B[c]中存放的总是当前长度为c的最长递增子序列中,最小的最末元素。
 
命题3:设第i次循环后得到的p为p(i+1),那么p(i)为以元素ai为最末元素的最长递增子序列的长度。
证明:只须证p(i)等于第二种算法中的f(i)。显然一定有p(i)<=f(i)。假设p(i)<f(i),那么有两种情况,第一种情况是由二分查找法找到的p(i)不是数组B中能让ai接在后面成为新的最长递增子序列的最大的元素,由命题1和二分查找的方法可知,这是不可能的;第二种情况是能让ai接在后面形成长于p(i)的最长递增子序列的元素不在数组B中,由命题2可知,这是不可能的,因为B[c]中存放的是最末元素最小的长度为c的最长递增子序列的最末元素,若ai能接在长度为L(L> p(i))的最长递增子序列后面,就应该能接在B[L]后面,那么就应该有p(i)=L,与L> p(i)矛盾。因此一定有p(i)=f(i),命题得证。
算法的循环次数为n,每次循环二分查找用时logn,所以算法的时间复杂度为O(nlogn)。这个算法在第二种算法的基础上得到了较好的改进。
 
五,    总结
 
本论文只给出了计算解的大小而没有给出构造解的方法,因为我认为计算解的大小的算法已能给出对问题的本质认识,只要计算解大小的算法设计出,构造解就只是技术细节的问题了,而我关心的是怎样对问题得到很好的认识而设计出良好的算法。以上几种算法已用Java实现,都能得到正确的结果。在设计和改进算法时用到了基本的算法设计和分析、证明的基本方法,很好的锻炼了设计与分析算法的思维能力,让我从感性上认识到算法分析与设计的重要性,并且感受了算法分析、设计和改进的乐趣。



本文转自Phinecos(洞庭散人)博客园博客,原文链接:http://www.cnblogs.com/phinecos/archive/2006/06/09/421884.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
18058 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
17566 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
23590 0
最长子序列和问题【最大子段和问题】
来源:http://blog.csdn.net/luxiaoxun/article/details/7438315 问题: 给定一整数序列A1, A2,... An (可能有负数),求A1~An的一个子序列Ai~Aj,使得Ai到Aj的和最大 例如:整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。
693 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
17419 0
+关注
4716
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载