最大子序列求和算法二 递归求解
递归求解:整个求解数组分成三部分,最大子序列可能出现在三个地方,左半部分,右半部分,跨越左右部分(包括左半部分最后一个元素,右半部分第一个元素)
分别对这三部分求解,不断的在每部分再分成三部分,递归求解
每一次递归跨越部分可以先算出,但是左,右半部分,需要不断递归,知道剩一个元素,然后回溯加上原来已经算出的跨越部分,最后返回max3(三个里面最大的一个)
时间复杂度计算
假设递归求解需要时间为T(N) ,N=1 时 T(1)=1
两个递归时间+两个for循环时间(假设一次一个时间单元)
两个递归时间 2T(N/2) +N/2+N/2=2T(N/2)+N
k表示序列号从0开始
N=2^k;T(N)=N*(k+1),T(N)=NlogN+N
所以 O(N)=NlogN
线性时间O(N) 算法
基于数学分析
设输入序列为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)开始重新求和,重复以上步骤即可得到最大子序列求和。
#include <stdio.h> int max3(int a, int b, int c); int maxSubSum1(const int array[], int left, int right) { int center,maxleftsum,maxrightsum; if (left == right) if (array[left] > 0) return array[left]; else return 0; center = (left + right) / 2; maxleftsum = maxSubSum1(array, left, center); maxrightsum = maxSubSum1(array, center + 1, right); int maxleftbodersum = 0, leftbordersum = 0, i; for (i = center; i >= left; i--) { leftbordersum += array[i]; if (leftbordersum > maxleftbodersum) maxleftbodersum = leftbordersum; } int maxrightbodersum = 0, rightbordersum = 0; for (i = center + 1; i <= right; i++) { rightbordersum += array[i]; if (rightbordersum > maxrightbodersum) maxrightbodersum = rightbordersum; } return max3(maxleftsum, maxrightsum, maxrightbodersum + maxleftbodersum); } int max3(int a, int b, int c) { int max = a; if (b > max) max = b; if (c > max) max = c; return max; } int maxSubSum2(int const array[],int N){ int maxsum=0,thissum=0,j; for(j=0;j<N;j++){ thissum+=array[j]; if(thissum > maxsum) maxsum = thissum; else if(thissum < 0) thissum = 0; } return maxsum; } int main(void) { int a[] = { 11, -2, 5, 8, 12, 6, -2, 4, -18, 7 }; printf("maxSubSum1 %d\n",maxSubSum1(a, 0, 9)); printf("maxSubSum2 %d",maxSubSum2(a, 10)); return 0; }
参考自 http://blog.csdn.net/superchanon/article/details/8228212
总结:优秀的算法是基于数学分析的基础上的
原文:http://www.cnblogs.com/loongqiang/p/3807189.html