<p class"1"="" style="text-indent:-18.0pt;">
一. 基本理论、特点
（一）问题描述
给定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 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]}，所以分析这类问题先从简单的穷举和分治入手，一步一步减少可节省的计算。
本文地址：https://www.stanwind.com/post/71
版权声明：若无注明，本文皆为“Make it Better”原创，转载请保留文章出处。
