最大子序列求解

《最大子序列求解》由会员分享，可在线阅读，更多相关《最大子序列求解（4页珍藏版）》请在装配图网上搜索。

1、最大子序列求解问题引入：在一串整数数列的一维方向上找到一个连续的子序列使其和最大。为方便起见，如果数列中含有负数，最大子序列和最小为0。求解这个问题的算法有很多种，本文将要分析穷举法，分治法和联机算法三种算法的优劣。理论上来讲，一个算法的复杂性越低，算法的运行效率越高，当然除了算法本身外，还有一些外部的因素也会影响算法是否合适，比如说只需要少量的输入，那就没有必要花费大把精力去研究精巧的算法，但如果大量输入，想要提高运行速率，好的算法还是非常有必要的。算法一穷举法这个算法实现起来较简单，只要穷举所有的可能，最后得出最大子序列和。具体做法就是先列出子序列第一个数的位置,然后枚举后面的元素并求和，

2、和前一个和比较大小，保留较大的值，知道最后一个。依次循环，直到穷举完所有的子序列。先看看算法是怎样实现的。intMaxSubsequenceSum(constintA,intN)intThisSum,MaxSum,i,j;/*对i进行遍历*/MaxSum=0;for(i=0;iN;i+)ThisSum=0;/*遍历以Ai开头的所有可能的子序列*/for(j=i;jMaxSum)MaxSum=ThisSum;returnMaxSum;这个算法中两个for循环穷举出了所有可能，复杂度为0（N2），效率不算太高，但对处理少量的数据基本上够用了。算法二分治法这个算法实现起来相对复杂一点，和上一个算法一

3、致，也是用了递归的方法。先说说什么是分治的思想，“分”就是把问题分成两个大致相等的子问题，“治”就是将两个子问题的解合并到一起并可能做一点附加工作，最后的到整个问题的解。在这个问题中，最大子序列可以有三种情况：整个出现在左半段或右半段，或者分布在左右两个部分。前两种情况递归求解即可，第三种情况可以分别求出前半段的最大和（包含最后一个元素），后半段的最大和（包含第一个元素），然后相加而得到。同样的来看看具体算法是怎样实现的。staticintMaxSubSum(constintA,intLeft,intRight)intMaxLeftSum,MaxRightSum;/声明左右两边的最大子序列in

4、tMaxLeftBorderSum,MaxRightBorderSum;/声明左右两边包含靠中间边界元素的醉的子序列intLeftBorderSum,RightBorderSum;声明左右两边子序列的和intCenter；/*处理基准情况，即在这里指只有一个元素*/if(Left=Right)if(ALeft0)returnALeft;elsereturn0;Center=(Left+Right)/2;/不用考虑奇偶的原因是C语言会自动向下取整MaxLeftSum=MaxSubSum(A,Left,Center);/递归调用，分出左边元素MaxRightSum=MaxSubSum(A,Cent

5、er+1,Right);/递归调用，分出右边元素/*求左边包含最后一个元素的最大子序列*/MaxLeftBorderSum=0;LeftBorderSum=0;for(i=Center;i=Left;i-)LeftBorderSum+=Ai;if(LeftBorderSumMaxLeftBorderSum)MaxLeftBorderSum=LeftBorderSum;/*求右边包含第一个元素的的最大子序列*/MaxRightBorderSum=0;RightBorderSum=0;for(i=Center+1;iMaxRightBorderSum)MaxRightBorderSum=Right

6、BorderSum;/*返回三种情况的最大值，这里调用了外部函数，并且包含隐式函数声明，需慎用*/returnMax3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);/*求3个数的最大值*/intMax3(longa,longb,longc)if(ac)returna;elsereturnc;intMaxSubsequenceSum(constintA,intN)returnMaxSubSum(A,0,N-1);这个算法的复杂度是O(NlogN)，具体分析过程尚未理解，待日后理解再加补充。算法三联机算法联机算法具有的特性：

7、只对数据进行一次扫描，一旦读入就不需要再记忆。在任意时刻都能把它已经读入的数据给出子序列的正确答案。本算法中有一个重要的思想，即当Ai为负数的时候，是不可能为最大子序列的起点的，下面我们来看看实现过程。intMaxSubsequenceSum(constintA,intN)intThisSum,MaxSum,j;ThisSum=MaxSum=0;for(j=0;jMaxSum)MaxSum=ThisSum;elseif(ThisSum0)ThisSum=0;returnMaxSum;这是一个常量空间并以线性时间运行的算法，其复杂度是0(N),运行效率颇高，是超大量数据分析的较佳算法。这个算法用

8、特值代替比较简单，但要理解为什么正确可能需要费点时间。这个算法可以和算法一相类比，算法一中i代表当前序列的起点，j代表终点。如果我们不需要知道最佳子序列的位置，那么i也就没有了存在的必要。由于Ai不能为负数，所以在循环中，如果我们检测到了从Ai到Aj的子序列是负数的时候，我们就可以向前推进i，类似的任何负的子序列都不可能是最佳子序列的前缀。例如说循环中我们检测到从Ai到Aj的子序列是负数那么我们就可以推进i，从i+1,i+2,i+3直推进到j+1j是使得从下标i开始成为负数的第一个下标，因此这样看来我们的i就可以消掉了。注意的是，虽然，如果有以Aj结尾的某序列和是负数就表明了这个序列中的任何一

9、个数不可能是与Aj后面的数形成的最大子序列的开头，但是并不表明Aj前面的某个序列就不是最大序列，也就是说不能确定最大子序列在Aj前还是Aj后，即最大子序列位置不能求出。但是能确保MaxSum的值是当前最大的子序列和。可以编译运行的程序，其他算法需要编译直接替换了就好，主函数部分不用修改。#includeintMaxSubsequenceSum(constintA,intN);intmain()intA=-2,11,-4,13,-5,-2,N;N=sizeof(A)/sizeof(A0);MaxSubsequenceSum(A,N);printf(length=%dn,N);printf(thesumofthemaxsubsequenceis%dn,MaxSubsequenceSum(A,N);return0;/*/intMaxSubsequenceSum(constintA,intN)intThisSum,MaxSum,j;ThisSum=MaxSum=0;for(j=0;jMaxSum)MaxSum=ThisSum;elseif(ThisSum0)ThisSum=0;returnMaxSum;