问题
概念：给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为：Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n。
一个数组a[]：需要求最大子段和的数组；
一个数组b[]：数组a子段和的数组，{a[0]，a[0]+a[1]，a[0]+a[1]+a[2]...........}；
例如，当(a[1],a[2],a[3],a[4],a[5],a[6])=(-2,11,-4,13,-5,-2)时，最大子段和为20。
解题
分治法
思路
如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出这两段的最大子段和，则a[1:n]的最大子段和：a[]:1..........................n分段处理:1..........n/2........n
三种情况
a[1:n]的最大子段和与a[1:n/2]的最大子段和相同（左边的子段和）a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同（右边的子段和）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]在最大子段中。
第3种情况：我们可以在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）的最大子段和。