分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。就像归并排序的排序思想一样。

回忆一下归并排序的过程，我们在递归地求解一个问题时，在每层递归中应用了以下三个步骤：

因此，从上面的思路我就便定义了两种情况：

最大子数组问题：给定一个整数数组，要求找出元素之和最大的子数组。即给你一个数组Arr[a1,a2,a3…,an]，求下标j,k，使得sum = a(j)+a(j+1)+a(j+2)+…+a(k)为最大值。

首先我们知道，只有数组中包含负数时，最大子数组问题才有意义，如果所有的数组元素都是非负的，那么最大子数组便是其本身。

对于最大子数组问题，有许多解法，如暴力穷举法，动态规划法等等，我们因为是为了学习分治的思想，因此主要讲用分治思想解最大子数组，其他方法可以参考如下博文：最大子数组及其优化

使用分治策略的求解方法：

加入给你如下数组A[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7],则最大子数组如下图所示：

下面我们来思考如何使用分治思想求解最大子问题，如过我们将原数组以其中心划分为两部分A[low,…,mid]和A[mid+1,…,high]，则我们要寻找的最大子数组一定只有三种可能位置。

如下图所示：

因此，我们可以递归地对前两种可能性求解，因为这两个子问题仍是最大子数组问题，只是规模相比较原数组更小，之后便是寻找跨越中点的最大子数组，然后在这三种情况中选取最大者。

对于跨越中点的最大子数组的求法，我们可以将这个数组A[i,…,mid,…,j]划分为两部分A[i,…,mid]和A[mid+1,…,j]，当这两部分分别为两边的最大子数组时，那么其合并起来的A[i,…,mid,…,j]即为跨越两边的最大子数组。

C语言实现：

解决了这个问题，那么接下来就简单了，按照上面讲的不断划分直到“触底”，然后寻找跨越两边的最大子数组，将三者比较返回最大的子数组。

分治算法解最大子数组的时间复杂度为O(n*log n),但是实际上还存在一个线性时间的算法，可参考最大子数组问题及其优化