紫书中所讲到的分治法第一次碰代码是有些懵逼的，结合陈越姥姥对于算法的引例的讲解，算是大概明白了是怎么回事。

我们知道一个经典问题是求一段序列中的最大连续和。

有三种做法可以解决:

一是暴力三层嵌套循环直接求出所有的连续序列和，进行比较即可

二是求出所有前缀和，之后后者减前者，算出每段的序列和比较。

前面两者的时间复杂度方法一为O（n^3），方法二为O（n^2）

这并不符合我们通常对于复杂度的理想情况

因此引出分治法，分而治之，提高效率

首先此问题是求最大连续和，那么我们可以假设在其中间划分出一条界线，对两边分别求其最大连续子序列和（这里向下递归）然后，求出分界线两边的最大连续和后，我们就此结束了吗

我们这里处理的只是分界线两边的连续序列，如果最大连续和是跨分界线的呢？

所以我们还要做一个新连续和，该连续和由分界线向左右两边发出，依次求出由分界线向左和由分界线向右的连续和（必须包括分界线），然后两边连续和相加即可

 

下面贴代码：

/* 第一步：先判断得到左半边的未跨中间线的最大子列和，然后得到右半边的最大子列和，
之后从中间线往两边延伸得到由中间值而得到的最大子列和，三者进行比较，取最大值即可 

第一步中可以得到左右两边未跨中间线的最大子列和，然后直接与跨边界的最大子列和即可 
*/
#include<stdio.h>
int a[10005];
int max(int a, int b){
	return a > b ? a : b;
}
int longsub(int a[], int l, int r){
	if(r-l == 1) return a[l];
	int mid = l + (r-l)/2;
	int maxs = max(longsub(a, l, mid), longsub(a, mid, r)); // 求得分界线两边的最大连续和，可以不包括分界线。 
	
	int v = 0, Lmax = a[mid-1], Rmax = a[mid]; // 注意：这里是初始化了由分界线向左右的初始值。 
	for(int i = mid-1; i >= l; i--)
		Lmax = max(Lmax, v += a[i]);   //求得分界线向左的最大连续子序列 
	
	v = 0;
	for(int i = mid; i < r; i++)
		Rmax = max(Rmax, v += a[i]);   //求得分界线向右的最大连续子序列 
	
	return max(maxs, Lmax+Rmax); 
	/* 这里所比较的是每一步对子序列的划分中所取的三者之中的最大值
	如a被划分后得到的a1， a2， a3三个最大值，其中a1是左半区域的最大值，a2是右半区域的最大值
	而a3是跨越划分a的分界线的最大值，这三者进行比较即可。  
	*/
}	
int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	printf("%d\n", longsub(a, 0, n));
	
	return 0;
}

具体复杂度为O（nlogn）。具体分析在陈越姥姥的数据结构第一讲中。