最大子段和的几种实现

我们知道最大子段和是指给出一组数字序列，在这个序列中有正有负，而最大的字段和就是指连续的几个数中，把这些数值加起来，求得最大的和，即为最大的子段和！

今天，我们讨论的就是如何求得最大的子段和！这个实现，有几种算法，我们一一讲述！我们假设当求得的最大和为负数的时候，规定为0！ 方法1：，我们讲述最简单的一种实现方式，也是最容易想到的就是用穷举法来实现！

这个原理其实是很简单，就是一组一组的试，这样找到最大的值！这是很容易想到的！详见代码！

1 #include 2 #define maxn 1000 3 int main() 4 {

5 printf(\"the num of zi duan:\\n\"); 6 int ziduan_len; 7 int a[maxn];

8 scanf(\"%d\

9 printf(\"please input the sequence of zi duan is :\\n\"); 10 for(int i=0;i14 int i,j,k;

15 int maxsum=0; 16 int besti,bestj; 17

18 for(i=0;i20 for(j=i;j22 int sum=0; 23 for(k=i;k25 sum+=a[k];

26 if(sum>maxsum) 27 {

28 maxsum=sum; 29 besti=i; 30 bestj=k; 31 } 32

33 } 34 } 35 }

女包、名牌包、背包:www.naitiao.com|冬装新款、流行冬装、今年流行秋冬装：dongzhuang.qqxk.net

36 printf(\"choose from %d to %d can make the sum of sequence the largest\\n\

37 printf(\"the largest sum is :%d \\n\38 return 0; 39 }

这个程序很浅显，就不再多说了！

我们可以把以上代码优化一下，上面的代码的时间复杂度为O(n的三次方），稍微优化后，时间复杂度变成了O(n的平方)! 请看优化后的代码！

#include #define maxn 1000 int main() {

printf(\"the num of zi duan:\\n\"); int ziduan_len; int a[maxn];

scanf(\"%d\

printf(\"please input the sequence of zi duan is :\\n\"); for(int i=0;iint i,j,k;

int maxsum=0; int besti,bestj;

for(i=0;ifor(j=i;jint sum=0;

sum+=a[j];

if(sum>maxsum) {

maxsum=sum; besti=i; bestj=k; }

} }

printf(\"choose from %d to %d can make the sum of sequence 女包、名牌包、背包:www.naitiao.com|冬装新款、流行冬装、今年流行秋冬装：dongzhuang.qqxk.net

the largest\\n\

printf(\"the largest sum is :%d \\n\ return 0; }

就是简单的去掉最后一个循环！

方法2 ：我们用动态规划的思想来解决这个问题！ 这个问题从数学的角度上来讲，就是一个这样的问题:

就是求 max{ a[k]的和} k从i 到j 其中 1<=i<=j<=n 状态转移方程 b[j]=max{b[j-1]+a[j],a[j]}, 1<=j<=n

1 #include 2 #define maxn 1000 3 int main() 4 {

5 printf(\"the num of zi duan:\\n\"); 6 int ziduan_len; 7 int a[maxn];

8 scanf(\"%d\

9 printf(\"please input the sequence of zi duan is :\\n\"); 10 for(int i=0;i13 int maxsum=0; 14 int b=0; 15

16 for(i=0;i19 int back_sum=b; 20 if(b>0) 21 {

22 b+=a[i]; 23

24 } 25 26 else

27 b=a[i];

28 if(b>back_sum) 29 maxsum=b; 30

31 }

32 printf(\"the largest sum is :%d \\n\33 return 0; 34 }

女包、名牌包、背包:www.naitiao.com|冬装新款、流行冬装、今年流行秋冬装：dongzhuang.qqxk.net

方法3：用分治算法来处理这个问题，将进一步降低时间复杂度至o(nlog(n)) 算法思想 :将 a[1:n]分成两段来求.整个子段的最大和无非有以下几种情况： 1.整个子段的最大和，是在a[1:n/2]中求得 2.整个子段的和是在a[n/2:n]中求得！

3.整个子段的最大和在中间求得，这个求最大和的过程中必定包含a[n/2]。

1 #include 2 #define maxn 1000

3 int maxsum(int *a,int left,int right) 4 {

5 int sum=0; 6 if(left==right)

7 sum=a[left]>0?a[left]:0; 8 else 9 {

10 int center =(left+right)/2;

11 int leftsum=maxsum(a,left,center);

12 int rightsum=maxsum(a,center+1,right); 13 int s1=0; 14 int lefts=0;

15 for(int i=center;i>=left;i--) 16 {

17 lefts+=a[i]; 18 if(lefts>s1) 19 s1=lefts; 20 }

21 int s2=0; 22 int rights=0;

23 for(int i=center+1;i<=right;i++) 24 {

25 rights+=a[i]; 26 if(rights>s2) 27 s2=rights; 28 }

29 sum=s1+s2; 30 if(sum35 }

36 return sum; 37 }

女包、名牌包、背包:www.naitiao.com|冬装新款、流行冬装、今年流行秋冬装：dongzhuang.qqxk.net

38 int main() 39 {

40 int a[maxn]; 41 int length; 42 int i;

43 scanf(\"%d\44 for(i=1;i<=length;i++) 45 scanf(\"%d\

46 int ans=maxsum(a,1,length);

47 printf(\"the max sum is %d\\n\48 49 50 }

这样实现后，将最大子段和的时间复杂度改为了O(nlogn)!

女包、名牌包、背包:www.naitiao.com|冬装新款、流行冬装、今年流行秋冬装：dongzhuang.qqxk.net