参考书籍： 算法导论 与书籍上相比改进点：在leftsum的起始值默认包含mid 的情况下，不让right包含第一个不匹配值，解决返回造成和原理论不符合的做法，虽然在每层几个递归返回的时候比较大小可以规避这个问题，但是确实存在
注： 这里称 mid 为确认点，因为mid 不一定为中点，只是为了变成方便和效率问题。但是中点更优秀，无奈我习惯了称确认点
合并
此算法的模型如下：分解 ： 最大子数组无非三种情况：过中间一确认点、或不过这一确认点（即在三点切分的两部分）求解 ： 当n =1 的时候 return 自己即(curIndex,curIndex,selfValue)。 当n != 1的时候，就分别递归分解成小问题，直到触底（也就是不可再分割），并在每一逻辑层做判断返回该逻辑层的最优解。具体看代码 我写了详细注释的合并 ： 在每层逻辑层返回给上一层的过程中，在逻辑判断下即最后的解为目的逻辑的解，即原命题最大子数组的解
代码如下： //用来保存子数组下表范围，子数组和的结构体 struct rtRAndV { int left; int right; int value; }; //过mid下标的最大子数组求解 rtRAndV findCrossing(int *Arr, int left, int mid, int right) { rtRAndV rt; //注： 这里0x80000000是设置的最大负数，因为mid下标所在的位置是确定有的（不然这个求解过mid的最大数组无意义了），而mid默认包含在left部分（Arr[mid]就无论如何也能计入）。而rightsum 初始化为0，防止把无用的第一个元素带入（这里和原著不同） int leftsum = 0x80000000, rightsum = 0, s = 0, leftmax = mid, rightmax = mid; for (int i = mid; i >= left; i--) { s = s + Arr[i]; if (s > leftsum)//第一次比较的时候就把mid 下表的数组元素给了leftsum { leftsum = s; leftmax = i; } } s = 0; for (int i = mid + 1; i <= right; i++) { s = s + Arr[i]; if (s > rightsum) { rightsum = s; rightmax = i; } } //这儿直接返回 找到的范围，其实该优化一下观察是否有相同的元素的。 rt.left = leftmax; rt.right = rightmax; rt.value = leftsum + rightsum; return rt; } //最大子数组分治 算法 递归 rtRAndV FindSubMaxArr(T *Arr, int left, int right) { int mid = (right + left) / 2; if (left == right) { rtRAndV rt = { left,left,Arr[left] }; return rt; } //后面这三个递归调用 的顺序无所谓，互不影响 //这个递归是调用求解右边的最大子数组的 rtRAndV rightsum = FindSubMaxArr(Arr, mid + 1, right); //递归求解左边的最大子数组 rtRAndV leftsum = FindSubMaxArr(Arr, left, mid); //过确认点mid 的最大子数组 rtRAndV cross = findCrossing(Arr, left, mid, right); //这里返回值的逻辑判断的顺序要留意下。如果处理不恰当，你得到的结果可能不是最优的，这就是前面的函数返回的是范围，不是元素 //比如Arr = {5,1,-1,2,-2,-4,-2,-3} 你得到的结果是 {0,4,5}，即中间无用的和值为0的子数组也添加进去了 //比如如下逻辑：优先选择cross造成的后果 //if (cross.value >= leftsum.value&&cross.value >= rightsum.value) //return cross; //else if (rightsum.value >= cross.value && rightsum.value >= leftsum.value)return rightsum; //else return leftsum; // if (leftsum.value >= cross.value&&leftsum.value >= rightsum.value) return leftsum; else if (rightsum.value >= cross.value && rightsum.value >= leftsum.value)return rightsum; else return cross; }