1.问题描述：给定一个数组，找出其中可以构成最大数的子段，子段和是由连续的子段构成的；给定有n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列连续的子段和的最大值。
2.设计思路：对于一个连续的子段和，如果把数组一分为二，那么最大的和有三种情况：在center的左边、右边，左右结合；所以只需要分别求出这三种情况的和，进行比较得到最大的和即可；其中的递归出口为right=left，也就是小子段中只剩下一个元素时结束递归。
3.代码：
/*二分法解决最大子段和问题*/
#include<stdio.h>
#include<math.h>
int array[6]={-20,11,-4,13,-5,-2}; //定义有六个元素的数组，保存信息
int array2[9]={-1,4,-3,1,5,-1,4,-5,2};
int bigger(int a,int b) //自定义一个求解最大数的函数
{return a>b ? a:b;}
int SubSegmentSum(int array[],int left,int right)
{int sum=0,leftsum=0,midsum=0,rightsum=0; //分别保存最后的sum、左边、中间、右边的最大子段和 int center; //中间分界线 int s1,lefts,s2,rights; //记录最大子段和为两边时的和 if(left==right) {sum=array[left]; //只有一个元素时sum=array[left]或者array[right] } else{center=(left+right)/2;//printf(" %d\n",center);leftsum= SubSegmentSum(array,left,center); //求左边的最大子段和rightsum=SubSegmentSum(array,center+1,right); //求右边的最大子段和s1=0,lefts=0;for(int i=center;i>=left;i--) //从中间开始往左边求最大子段和 {lefts+=array[i];if(lefts>s1){s1=lefts;}} s2=0,rights=0;for(int i=center+1;i<=right;i++) //从中间开始往右边求最大子段和 {rights+=array[i];if(rights>s2){s2=rights;}}midsum=s1+s2; //中间的最大子段和 sum=bigger(bigger(leftsum,rightsum),midsum); //求解最大子段和 }return sum;
}
int main()
{int sum1=SubSegmentSum(array,0,5);int sum2=SubSegmentSum(array2,0,8);printf("%d\n",sum1);printf("%d\n",sum2);return 0;
}4.运行结果：
5.总结：
最大子段和问题，关键是清楚连续的最大子段和的三种情况：左边、右边和左边加右边，分别求出三种情况下的最大子段和，进行比较即可以得到最大的子段和。
