首页 > 代码库 > 最大子序列和算法分析——好的算法对于编程是多么重要！！！
最大子序列和算法分析——好的算法对于编程是多么重要！！！
昨天晚上在宿舍看Mark Allen Weiss老爷子的《数据结构与算法分析Java语言描述》的这本书，看到第二章的时候举了个例子来讨论，就是关于最大子序列和的算法分析。一共提了四个算法，首先当你看见第一个算法的时候觉得这个算法不错，可以实现，再接着当你看到后面连着的三个例子的时候这才明白算法一步步的优化对于整个性能的提升，有时候我们不是想不出来好的算法，只是当第一种算法出来得时候我们的思维已经被局限化了，觉得是对的就以为是唯一解了，实感唏嘘！ 早上来到实验室特地找了一些资料，贴在这里，以后多学习多看看好的算法！
Maximum Continuous Subsequence Sum
最大连续子序列求和详解
1. 问题描述
输入一个整数序列（浮点数序列也适合本处讲的算法），求出其中连续子序列求和的最大值。
2. 算法分析
2.1. 算法一
2.1.1. 算法描述
遍历所有子序列并求和，比较得出其中的最大值。
2.1.2. 代码描述
1 public static int maxSubSumCubic(int[] array) { 2 int maxSum = 0; //最大子序列求和 3 //start表示要求和的子序列的开始索引，end表示结束索引 4 for(int start = 0; start < array.length; start++) { 5 for(int end = start; end < array.length; end++) { 6 int thisSum = 0; //当前子序列求和 7 //求出array[start]~array[end]子序列的和 8 for(int index = start; index <= end; index++) { 9 thisSum += array[index]; 10 } 11 //判断是否大于之前得到的最大子序列求和 12 if(thisSum > maxSum) { 13 maxSum = thisSum; 14 } 15 } 16 } 17 return maxSum; 18 }
2.1.3. 算法分析
设输入序列长度为N，算法一有三个循环嵌套，第4行的循环长度为N。第5行的循环长度为N-start+1，因为我们考虑的是最差性能，所以可取为最大的N。第8行的循环长度是end-start+1，同理可取为N。所以可得算法的运行时间是O(N*N*N)=O(N^3 )，即算法的运行时间是以输入长度的立方增长的。可想而知，一旦输入长度变大，算法的运行效率将慢得无法接受，这也从反面说明了算法设计的重要性。
2.2. 算法二
2.2.1. 算法描述
算法设计的一个重要原则就是“不要重复做事”。在算法一中，对array[start]~array[end]子序列求和，可以由上一次求和array[start]~array[end-1]的结果加上array[end]得到，而不用从头开始计算。
2.2.2. 代码描述
1 public static int maxSubSumQuadratic(int[] array) { 2 int maxSum = 0; //最大子序列求和 3 //start表示要求和的子序列的开始索引，end表示结束索引 4 for(int start = 0; start < array.length; start++) { 5 int thisSum = 0; //当前子序列求和 6 for(int end = start; end < array.length; end++) { 7 //已求得的array[start]~array[end-1]子序列的和加上array[end] 8 //得到array[start]~array[end]子序列的和 9 thisSum += array[end]; 10 //判断是否大于之前得到的最大子序列求和 11 if(thisSum > maxSum) { 12 maxSum = thisSum; 13 } 14 } 15 } 16 return maxSum; 17 }
2.2.3. 算法分析
算法二比算法一少了一个循环，同之前的分析一样，容易得到该算法的运行时间为O(N^2)，算法的运行时间是以输入长度的立方增长的。
2.3. 算法三
2.3.1. 算法描述
考虑把输入序列从中间分成两半，那么最大和子序列的位置存在三种情况：1、最大和子序列完全在输入序列的左半部分；2、最大和子序列完全在输入序列的右半部分；3、最大和子序列跨越左右两部分。
所以，为了得到输入序列的最大子序列和，我们可以分别求出左半部分的最大子序列和、右半部分的最大子序列和、以及跨越左右两部分的最大子序列和，比较三者得出最大者就是要求的。
求左半部分的最大子序列和，可把左半部分作为新的输入序列通过该算法递归求出。右半部分的最大子序列和也同理。
接下来就是求解跨越左右两部分的最大子序列和，也就是求出左半部分中包含最右边元素（如图中的12）的子序列的最大和，和右半部分中包含最左边（如图中的6）的子序列的最大和，将两者相加即为跨越左右两个部分的最大子序列和。
另外还有一个需要说明的就是，对于有奇数个元素的数组，那么左右两半部分并不是平分的，但这其实不是问题。上面的算法并不要求是两半部分，分成任意两部分都可以。
2.3.2. 代码描述
1 public static int maxSubSumRec(int[] array, int left, int right) { 2 //递归的基准情况:待处理序列只有一个元素 3 if(left == right) { 4 //空集也算是子序列，空集和为0，所以最大子序列和最小为0 5 if(array[left] > 0) 6 return array[left]; 7 else 8 return 0; 9 } 10 11 //递归求出左半部分和右半部分的最大子序列和 12 int center = (left + right) / 2; 13 int maxLeftSum = maxSubSumRec(array, left, center); 14 int maxRightSum = maxSubSumRec(array, center + 1, right); 15 16 //求出左半部分中包含最右边元素的子序列的最大和 17 int maxLeftBorderSum = 0, leftBorderSum = 0; 18 for(int i = center; i >= left; i--) { 19 leftBorderSum += array[i]; 20 if(leftBorderSum > maxLeftBorderSum) { 21 maxLeftBorderSum = leftBorderSum; 22 } 23 } 24 25 //求出右半部分中包含最左边元素的子序列的最大和 26 int maxRightBorderSum = 0, rightBorderSum = 0; 27 for(int i = center + 1; i <= right; i++) { 28 rightBorderSum += array[i]; 29 if(rightBorderSum > maxRightBorderSum) { 30 maxRightBorderSum = rightBorderSum; 31 } 32 } 33 34 //跨越两个部分的最大子序列和 35 int maxLeftRightSum = maxLeftBorderSum + maxRightBorderSum; 36 37 //maxLeftSum、maxRightSum、maxLeftRightSum中的最大值即为最大子序列和 38 int maxSubSum = 0; 39 maxSubSum = maxLeftSum > maxRightSum ? maxLeftSum: maxRightSum; 40 maxSubSum = maxSubSum > maxLeftRightSum ? maxSubSum: maxLeftRightSum; 41 42 return maxSubSum; 43 }
2.3.3. 算法分析
设T(N)表示输入序列长度为N时的运行时间，若N=1，即只有一个元素，那么left==right，所以有T(1)=1。对于N>1，程序需运行两个递归调用和两个for循环。其中每个递归调用的运行时间相当于输入长度为N/2时算法的运行时间T(N/2)，两个递归则为2T(N/2)。每个for循环的运行次数为N/2，循环体中的语句运行时间是常数，所以两个for循环的运行时间为O(N/2*2)=O(N)。所以对于N>1，有T(N)=2T(N/2)+O(N)，为了方便，可用N代替O(N)，数量级不变，所以T(N)=2T(N/2)+N。在Weiss的《数据结构与算法分析Java语言描述（第二版）》中，作者通过观察的方式得出T(N)=N*(K+1)，其中N=2^k ，所以有T(N)=N*(k+1)=NlogN +N=O(N )。
这里笔者自己尝试推导出这个结果，如有疏误或更好的方法，请不吝指教。同样，假设N为2的K次方，如果不是2的K次方，直接推导可能会比较复杂。当然我们可以这么理解，如果N不是2的K次方，可以通过在输入序列开头加入n个0，使N=N+n变成2的K次方。因为增加了输入的长度，所以运行时间比原本的要长，因为算法分析是最差时的性能，所以能用变长了的运行时间来代替原来的运行时间。所以问题同样转化成N为2的K次方时，T(N)的表示式怎么求。好了，废话不多说，直接推导。
由T(N)=2T(N/2)+N两边同除以N，得
(T(N))/N=(T(N/2))/(N/2)+1 => (T(N))/N-(T(N/2))/(N/2)=1
令F(N)=(T(N))/N ，则有
F(N)-F(N/2)=1
往下递推有
F(N/2)-F(N/4)=1
...
F(2) - F(1)=1
以上K(=logN )个式子相加可得
F(N)-F(1)=1+...+1=logN
即
T(N)/N-T(1)/1=logN
可得
T(N)=N logN+N=O(N logN)
由以上推理过程可得该算法的运行时间为
T(N)=O(N logN)
2.4. 算法四
2.4.1. 算法描述
设输入序列为A，长度为N，从a0开始求和并记录最大值，如a(0)，a(0)+a(1)，a(0)+a(1)+a(2)…，直到开始出现求和小于0则停止。设加到a(i)时开始小于0，即有a(0)，a(0)+a(1)，…，a(0)+…+a(p-1)都大于0，而a(0)+a(1)+…+a(p)<0。此时，可从a(p+1)重新开始求和并记录最大值。为什么可以这么做呢？我们把从a(1)到a(p)之间开始的子序列分为两种情形（设子序列的开始索引为start，结束索引为end）：
1、end<=p，a(start)+…+a(end)=a(0)+…+a(start)+…a(end) –[a(0)+…+a(start-1)]。由前面知，对于start-1<p，有a(0)+…+a(start-1)>0，所以可得到a(0)+…+a(start)+…a(end)> a(start)+…+a(end)。又由于a(0)+…+a(start)+…a(end)已经考虑过了，所以比其小的子序列无需考虑。
2、end>p，因为1<=start<=p，有a(0)+…+a(start-1)>0而a(0)+…+a(start)+…a(p)<0，所以有a(start)+…a(p)= a(0)+…+a(start)+…a(p)-[ a(0)+…+a(start-1)]<0。对于end>p，有a(start)+…+a(p)+…+a(end)<a(p+1)+…a(end)。
综上所述，只需要从a(p+1)开始重新求和，重复以上步骤即可得到最大子序列求和。
2.4.2. 代码描述
1 public static int maxSubSumLinear(int[] array) { 2 int maxSum = 0, thisSum = 0; 3 for(int j = 0; j < array.length; j++) { 4 thisSum += array[j]; 5 if (thisSum < 0) { 6 thisSum = 0; 7 } 8 else if(thisSum > maxSum) { 9 maxSum = thisSum; 10 } 11 } 12 return maxSum; 13 }
2.4.3. 算法分析
算法四只有一个for循环，且循环里面语句的执行时间为常量，所以T(N)=O(N)。可见该算法的运行时间是线性增长的，比前三个算法的性能要好。另外一个优点就在于该算法每次就需要使用一个输入值array[j]，所以如果是在硬盘或者网络传输的环境下，我们可以实现串行读取，减少内存占用。
转自：http://blog.csdn.net/superchanon/article/details/8228212
References：
《数据结构与算法分析Java语言描述（第2版），Mark Allen Weiss
最大子序列和算法分析——好的算法对于编程是多么重要！！！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。