利用分治法求最大子段和问题，同时求出最优解 给定长度为 n 的整数序列，a[1...n], 求[1,n]某个子区间[i , j]使得 a[i]+…+a[j]和最大.或者求出 最大的这个和. 例如(-2,11,-4,13,-5,2)的最大子段和为 20,所求子区间为[2,4]. 如果该序列的所有元素都是负整数时定义其最大子段和为 0。 2、最大子段和问题的分治法： 求子区间及最大和，从结构上是非常适合分治法的，因为所有子区间[start, end]只可 能有以下三种可能性: 在[1, n/2]这个区域内 在[n/2+1, n]这个区域内 起点位于[1,n/2],终点位于[n/2+1,n]内 分治法思路如下： 将序列 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]的最大字段和为 ，且 1<=i<=n/2,n/2+1<=j<=n。 可用递归方法求得情形[1],[2]。对于情形[3],可以看出 a[n/2]与 a[n/2+1]在最优 子序列中。因此可以在 a[1:n/2]中计算出 ，并在 。则 s1+s2 即为出现情形[3]时 a[n/2+1:n]中计算出 的最优值。 算法所需的计算时间 T(n)满足一下递归式： T(n)=2T(n/2)+O(n) **T(n)=O(nlogn) 

解此递归方程可知：T(n)=O(nlogn)。 [cpp] view plaincopy //最大子段和，分治算法。T(n)=O(nlog(n))。 #include using namespace std; int MaxSubSum(int a[],int left,int right) { int sum = 0; if(left == right) sum = a[left] > 0 ? a[left] : 0; else { int center = (left + right) / 2; int leftsum = MaxSubSum(a, left, center); int rightsum = MaxSubSum(a, center + 1, right); int s1 = 0; int lefts = 0; for(int i = center; i >= left; i--) { lefts += a[i]; if(lefts > s1) s1 = lefts; } int s2 = 0; int rights = 0; for(int i = center + 1; i <= right; i++) { rights += a[i]; if(rights > s2) s2 = rights; } sum = s1 + s2; if(sum < leftsum) sum = leftsum; if(sum < rightsum) sum = rightsum; } return sum; } int main() { int n,a[100],m,maxsum; cout<<"请输入整数序列的元素个数 n:"<

cin>>n; cout<<"请输入序列中各元素的值 a[i](一共"<>a[m]; int b[100]; for(m=0;m