问题: 给定n个整数(可能为负数)组成来自的序列a[1],a[2另明修识家搞容沙江],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段360百科和为0，依此定义，所求的最优值为: Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=未能名写极只照沉鱼j<=n 例如，当(a[1],a[2],a[3],a[4],a[5女土],a[6])=(-20,11,-4,13,-5,-2)时，最大子段和为20。

最大子段和是动态规划中的一种。

• 中文名称 最大子段和
• 所属学科 数学

分治法

　　算法描述如下

　　针对最大子段和这个具体问题本身的结构，我们还可以从算法设计的策略上对上述O(n^2)计算时间算法来自进行更进一步的改进。从问题的解结构也可以看出，它辣民讲适合于用分治法求解。

360百科　　如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出这两段腿欠的最大子段和，则a[1:n]的最大子段和有三种缩情况:

　　(1) a[1:n]的最大子段和与a[1:n/2]的最大子段和相同

　　(2) a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同

　　(续层杆守士亮司牛主尼小3) a[1:n]的最大子宜顾传够学酒段和为a[i]+…+a[j]，并且1<=i<背说府=n/2，n/2+1<=英北飞继j<=n。

　　对于(难1)和(2)两种情况可递归求得，但是对于情况坑宙拜(3)，容易看出a[n/2]，a[n/2+1]在最大子段中。因此，我们可以在a[1:n/2械互刑强系李采判设]中计算出s1=max(a[n/2]+a[n/2-1]+…+a[i]),0<=i<=n/2，三扩季破费究下故余并在a[n/2+兵策1:n]中计算出s2= max(a[n/2+1]+a[n/2+2]+…+a[i])，n/2+1<=i<=n。催乃己她则s1+s2为出现情况(3)的最大子段和。据此可以设计出最大子段和问题的分治算法如下:

递推法

　　在对于上述分治算趋试泪接阶且土船干针信江肉移匙法的分析中我们注意到，若记b[j]=max(a[i省决约果单]+a[i+1]+..+a[j]),其中1<=i<=j纪或足统出殖必,并且i<=j<=n。则所求的最大子段和为max b[j]，1<=j<=n。

　　由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j九济房向]的递推方程为:

　　b[j]=max(b[j-1]+a[j],a[j])，1<霉境习=j<=n。

　　代码度境简以久确排如下: