首先，我们要知道，什么是分治法？分治法有什么用？什么情况下使用？这些就是比较正常的想法了，好啦，我们接下来开始分析。
一，什么是分治法？
将整个问题分解成若干个小问题后再分而治之。如果觉得得到的子问题的规模还是太大，那就继续分解，直到得到的子问题规模达到要求。必要时逐步合并这些子问题的解，从而得到问题的解。
大家是不是觉得很眼熟？
是不是很像递归的过程，规模逐渐减小。所以，一般来说，分治算法一般由递归来实现。因为分治法就是反映的大规模问题和小规模问题之间的关系。
int Max3(int a, int b, int c) { return a > b ? a > c ? a : c : b > c ? b : c; } int DivideAndConquer(int List[], int left, int right) { //分治法求List[left]到List[right]的最小子列和 int MaxLeftSum, MaxRightSum;//存放左右子问题的解 int MaxLeftBorderSum, MaxRightBoderSum;//存放跨分界线的结果 int LeftBorderSum, RightBorderSum; int center, i; if (left == right) {//递归的结束条件，子列只有一个数字 if (List[left] > 0) return List[left]; else return 0; } //下面是分的过程 //找到中分点 center = (left + right) / 2; //递归求两边子列的最大和 MaxLeftSum = DivideAndConquer(List, left, center); MaxRightBoderSum = DivideAndConquer(List, center + 1, right); //下面求跨分界线最大子列和 MaxLeftBorderSum = 0; LeftBorderSum = 0; for (i = center; i >= left; i--) { LeftBorderSum += List[i]; if (LeftBorderSum > MaxLeftBorderSum) MaxLeftBorderSum = LeftBorderSum; } //左边扫描结束 MaxRightBoderSum = 0; RightBorderSum = 0; for (i = center + 1; i <= right; i++) { RightBorderSum += List[i]; if (RightBorderSum > MaxRightBoderSum) MaxRightBoderSum = RightBorderSum; } //右边扫描结束 //最后进行比较 return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBoderSum); } int MaxSubseqsum3(int List[],int N) { return DivideAndConquer(List, 0, N - 1); }
二，在线处理
“在线”的意思是指每输入一个数据就进行即时处理，得到的结果是对于当前已经读入的所有数据都成立的解，即在任何地方中止输入，算法都能正确给出正确的解。
这种算法并不要求存储序列中的数据，只需要一个一个读入，同时一个一个处理即可，处理过的数据没必要存储，可以说是最快的算法了。
int MaxSubseqSum4(int List[], int N) { int i; int ThisSum, MaxSum; ThisSum = MaxSum = 0; for (i = 0; i < N; i++) { ThisSum += List[i]; if (ThisSum > MaxSum) MaxSum = ThisSum; else if (ThisSum < 0) ThisSum = 0; } return MaxSum; }
