绝妙的算法——最大子序列和问题

《绝妙的算法——最大子序列和问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要 本文分析并演示最大子序列和问题的几种算法，它们都能解决问题，但是时间复杂度却大相径庭，最后将逐步降低至线性。算法 子序列和问题的引入    给定（可能有负数）整数序列A1,A2,A3...,An，求这个序列中子序列和的最大值。（为方便起见，如果所有整数均为负数，则最大子序列和为0）。例如：输入整数序列：-2,11,8,-4,-1,16,5,0，则输出答案为35，即从A2～A6。    这个问题之所以有吸引力，主要是因为存在求解它的很多算法，而这些算法的性能差异又很大。这些算法，对于少量的输入差别

2、都不大，几个算法都能在瞬间完成，这时若花费大量的努力去设计聪明的算法恐怕就不太值得了；但是如果对于大量的输入，想要更快的获取处理结果，那么设计精良的算法显得很有必要。切入正题    下面先提供一个设计最不耗时间的算法，此算法很容易设计，也很容易理解，但对于大量的输入而言，效率太低：    算法一：摘要 本文分析并演示最大子序列和问题的几种算法，它们都能解决问题，但是时间复杂度却大相径庭，最后将逐步降低至线性。算法 子序列和问题的引入    给定（可能有负数）整数序列A1,A2,A3...,An，求这个

3、序列中子序列和的最大值。（为方便起见，如果所有整数均为负数，则最大子序列和为0）。例如：输入整数序列：-2,11,8,-4,-1,16,5,0，则输出答案为35，即从A2～A6。    这个问题之所以有吸引力，主要是因为存在求解它的很多算法，而这些算法的性能差异又很大。这些算法，对于少量的输入差别都不大，几个算法都能在瞬间完成，这时若花费大量的努力去设计聪明的算法恐怕就不太值得了；但是如果对于大量的输入，想要更快的获取处理结果，那么设计精良的算法显得很有必要。切入正题    下面先提供一个设计最不耗时

4、间的算法，此算法很容易设计，也很容易理解，但对于大量的输入而言，效率太低：    算法一：public static int maxSubsequenceSum(int[] a) {     int maxSum = 0;     for(int i=0; i

5、          for(int k=0; k<=j; k++)        //迭代子序列中的每一个元素，求和                 thisSum += a[k];             if(thisSum > maxSum)                 maxSum = thisSum;         }     }     return maxSum; }    上述设计很容易理解，它只是穷举各种可能的结果，最后得出最大的子序列和。毫无疑问，这个算法能够正确的得出和，但

6、是如果还要得出是哪个子序列，那么这个算法还需要添加一些额外的代码。    现在来分析以下这个算法的时间复杂度。运行时间的多少，完全取决于第6、7行，它们由一个含有三重嵌套for循环中的O(1)语句组成：第3行上的循环大小为N，第4行循环大小为N-i，它可能很小，但也可能是N。我们在判断时间复杂度的时候必须取最坏的情况。第6行循环大小为j-i+1，我们也要假设它的大小为N。因此总数为O(1*N*N*N)=O(N3)。第2行的总开销为O(1)，第8、9行的总开销为O(N2)，因为它们只是两层循环内部的简单

7、表达式。    我们可以通过拆除一个for循环来避免3次的运行时间。不过这不总是可能的，在这种情况下，算法中出现大量不必要的计算。纠正这种低效率的改进算法可以通过观察Sum(Ai~Aj)=Aj+Sum(Ai~A[j-1])而看出，因此算法1中第6、7行上的计算过分的耗费了。下面是在算法一的基础上改进的一种算法：    算法二：public static int maxSubsequenceSum(int[] a) {     int maxSum = 0;     for(int i=0; i

8、ength; i++) {         int thisSum = 0;         for(int j=i; j maxSum)                 maxSum = thisSum;         }     }     return maxSum; }    对于此算法，时间复杂度显然是