对最大子段和算法的实例评述

2018-1-30 StanWind

一. 基本理论、特点

（一）问题描述

给定n个整数(可能为负数)组成序列a1,a2,a3…,an，求该序列形如

（二）基本理论

首先想到的解决算法就是穷举，枚举出所有情况然后比较子段和大小得出结果，这其中得出所有情况的和过程中，计算有重复可以稍加分析优化；然后是分治法，把这一串序列不断细化，求解出每一段的子段和进行比较得出结果。

（三）特点

需要求子段和需要前后两个下标位置，穷举法得出结果复杂度必然很高；分治法求解时会发生结果出现在分开处，需要考虑这一段的最大子段和求解，复杂度将会大于等于O(nlogn)。

二. 求解过程

求一下序列的最大字段和：

【 31 40 -38 41 13 -41 -23 4 45 46
-35 47 45 -2 30 -36 -8 41 29 45 15 -47 34 43 17 25
24-11 15-33 20-47 -23-46-41 32 19-19 45-47 -7-12 26 29-32 -2 -6 14 20 25-23 17 15-34-39 -1 45-16 8- 28 25-25 0 19 39 45 4-37-36-25
34- 25 31-26 42-16-31-25 11 -3 -15 33 8 4 41-22 25
25-12 6-43-45 3 27 43-38 6 -4-49-17 】

（一）分析问题

这里给定了100个整数，需要求解出最大子段和。这个问题其实就是从给定的一串序列中求其子连续序列的最大值。那么可以用sum(i,j)来表示a[i]+a[i+1]+…+a[j]
(0>=i>=j>=n)，那么经过穷举过后就可以比较得出最大子段和。

（二）算法设计与论证

1.穷举法

如上面求解分析所说，只需要枚举出所有可能的i,j后进行求和就能得出结果。但是枚举出所有可能就有两层循环，之后计算i->j的和又有一层循环，复杂度是O(n3)。

2.分治法

分治法求解这个问题无非就是将序列不断细分，这题中分解成左右两部分，但是最大子段和可能发生在任何几个连续数之间，即结果也可能发生在分解序列之间。则left_max
= max(left,center),right_max=max(center+1,right),center_max=sum(i,j)
(i<=center<=j)。

3.动态规划法

如上穷举法求和方面计算sum(i,j)之后需要继续计算sum(i,j+1)，如果更改循环结构，并且存储好上次结果能很好的降低复杂度。这样的话不难得出sum(i,j)
= sum(i,j-1)+a[j]。

那么在最大值方面，如果sum(i,j-1)>=0,那么下个值sum(i,j)则可能选为最大值，即max(i,j);如果sum(i,j-1)<0,那么下个推算出的最大值应为max(i,j)=a[j]。那么只需要遍历一遍该序列就可以得出结果，复杂度为O(n)。

（三）伪代码

1.动态规划

function
<max>(a[N] Integer)

m[N] Integerß{0}

maxß0

for iß1 to N do

if m[i-1]>0 then

m[i]=m[i-1]+a[i]

else

m[i]=a[i]

end if

if b[i]>max then

max=b[i]

end if

end for

return
max

2.分治法

function <max>(left Integer,right
Integer)

l_max,r_max,max,l_sum,r_sum,sumß0

if
left = right then

if a[left] > 0 then

return a[left]

else

return 0

end if

else

l_max = max(left,center)

r_max = max(center+1,right)

for i:=1 to left do

sum=sum+a[i]

if sum > l_sum then

l_sum=sum

end if

end for

sumß0

for i:=center+1 to right do

sum=sum+a[i]

if sum > r_sum then

r_sum=sum

end if

end for

max = l_sum+r+sum

if l_max>max then

max = l_max

end if

if
r_max>max then

max = r_max

end if

return
max

（四）问题求解

1.算法实现(C语言)

（1）动态规划

#include<stdio.h>

#define MAX 100

int maxsub(int left,int right);

int a[MAX];

int main(){

int i;

int count;

scanf("%d",&count);

for(i=0;i<count;i++)

{

scanf("%d",&a[i]);

}

//DP

// 创建存储和的数组

int m[MAX] = {0};

m[0] = a[0];

//如果前段和>0 则下一个最大和为前段加下个值否则为下个值

int max = 0;

for(int i=1;i<count;i++){

if(m[i-1]>0){

m[i]=b[i-1]+a[i];

}

else{

m[i]=a[i];

}

//然后判断这次是不是最大值

max = m[i]>max?m[i]:max;

}

printf("max = %d
\n",max);

return 0;

}

（2）分治法

int maxsub(int left,int right) {

int l_max,r_max,max = 0;

int l_sum=0,r_sum=0,sum = 0;

int center =
(left+right)/2;

if(left==right){

//递归出口

return a[left]>0?a[left]:0;

}else{

//出现在两边

l_max = maxsub(left,center);

r_max = maxsub(center+1,right);

//出现在两段之间从中间往两边求最大

//左边

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

sum+=a[i];

if(sum>l_sum)

l_sum=sum;

}

//右边

sum=0;

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

sum+=a[i];

if(sum>r_sum)

r_sum=sum;

}

max = l_sum+r_sum;

if(l_max>max)

max = l_max;

if(r_max>max)

max = r_max;

return max;

}

2.控制台结果

从m数组看71->33->74->87->46->23->27->72->118->83->130->175->173->203->167->159->200->229->274->289->242->276->319->336->361->385->374->389->356->376->329->306->260->219->251->270->251->296->249->242->230->256->285->253->251->245->259->279->304->281->298->313->279->240->239->284->268->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276,该最大值发生在a[26],m[i]<a[i]分支执行0次，则前段数据未发生抛弃，则最大子段和为sum(0,26)。

三总结分析

用DP求解该问题需要一步步分析，得出递推式是关键。上题中通过穷举和分治不难推算出DP递推式为m[i]=max{m[i-1]+a[i],a[i]}，所以分析这类问题先从简单的穷举和分治入手，一步一步减少可节省的计算。

发表评论：