摘要
分治就是将原问题不断拆分成规模小的问题，直到小问题可以得出答案为止，然后再往上推导出原问题的答案。拆分的问题必须要和原问题结构是一致，这和递归的解答思路较大程度上是一致的。
分治，可以理解为分而治之，核心逻辑就是将原问题分解成若干个小问题，原问题和小问题在结构上是一致的，唯一的区别就是规模不同。然后再将小问题分解出更小的问题，直到无法再分解为止，也就是可以直接或者简单的计算得出问题的答案。最后利用小问题推导出原问题的解。
这个和递归的思想类似，所以分治策略非常适合使用递归来处理，需要特别注意的是，分治策略中的子问题都是相互独立的。
可以应用到分治策略的有快速排序、归并排序和大数乘法等。
递归思想的拆解问题和求解
递归的思想就是将规模大的问题，拆分成规模较小的同类问题，然后将规模较小的问题再拆分成规模更小的同类问题，直到可以直接得出问题的解为止，然后通过这个解推到出原问题的答案。
通用模式
分治策略通常遵循这样的通用模式，解决规模为 n 的问题，就分解成 a 个规模为 n b \frac{n}{b} bn 的子问题，然后在 O( n d n^d nd) 时间内将子问题的解给合并起来。
总结下来，算法运算的时间 T(n) = aT( n b \frac{n}{b} bn) + O( n d n^d nd)，a > > > 0，b > > > 1，d ≥ \geq ≥ 0。 继续简化运算时间的公式，有以下三个公式：
- d < < < l o g b a logb^a logba，T(n) = O( n d n^d nd)；
- d = l o g b a logb^a logba，T(n) = O( n d l o g n n^dlogn ndlogn)；
- d < l o g b a logb^a logba，T(n) = O( n ( l o g b a ) n^(logb^a) n(logba))
求最大连续子序列和
接下来通过求最大连续子序列和来进一步了解下分治策略。
当给定一个长度为 n 的整数序列，求它的最大连续子序列和，比如整数序列为 -2、1、-3、4、-1、2、1、-5、4，那么这个整数序列的最大连续子序列和是 4 + (-1) + 2 + 1 = 6。
子串、子数组、子区间是连续的，子序列是可以不连续的。
那么最简单的实现，就是暴力求解，找出所有连续子序列的和，比较出最大的那个。如下代码所示，用三个 for 循环来找出所有的连续子序列，并比较出最大值。
int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int max = Integer.MIN_VALUE;
for (int begin = 0; begin < nums.length; begin ++) {
for (int end = begin; end < nums.length; end++) {
int sum = 0;
for (int i = begin; i <= end; i++) {
sum += nums[i];
}
max = Math.max(max, sum);
}
}
return max;
}
看上面的代码，可以计算出空间复杂度是 O(1)，时间复杂度是 O( n 3 n^3 n3)。函数中可以继续优化，重复使用前面计算出的 sum 值，代码如下所示：
int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int max = Integer.MIN_VALUE;
for (int begin = 0; begin < nums.length; begin ++) {
int sum = 0;
for (int end = begin; end < nums.length; end++) {
sum += nums[end];
max = Math.max(max, sum);
}
}
return max;
}
优化后的函数，它的空间复杂度是 O(n)，时间复杂度减少为 O( n 2 n^2 n2)。
分治求最大子序列和
现在用分治策略来求最大子序列和。先将序列均匀的分割成两个子序列 [begin, end) = [begin, mid) + [mid, end)，mid = (begin + end) >> 1。
‘[’ 表示大于并等于
‘)’ 表示小于
假设[begin, end) 的最大子序列是 S[i, j)，那么它就有三种可能情况：
1、 S[i,j)在[begin,mid)中；
2、 S[i,j)在[mid,end)中；
3、 S[i,j)一部分在[begin,mid)中，一部分在[mid,end)中；
当出现第3种情况时，继续往下分析：
1、 [i,j)=[i,mid)+[mid,j)，公式成立；
2、 S[i,mid)=max{S[k,mid)}，begin≤\leq≤k<<<mid；
3、 S[mid,j)=max{S[mid,k)}，mid≤\leq≤k<end；
所以用代码实现时，就是将这三种情况都给求解出来，然后比较这3种情况的解，其中最大的就是这个序列的连续子序列和。
先创建一个对外调用的函数，设置 nums 数组异常的处理，如下代码所示：
static int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
return maxSubArray(nums, 0, nums.length);
}
然后创建一个求连续子序列和的函数，传入 nums 的同时，也要传入 begin 和 end，在这个函数中要实现 S[i, j) 的三种情况，第一种情况用 maxSubArray(nums, begin, mid) 处理，第二种情况用 maxSubArray(nums, mid, end) 来处理。这种处理方式就是递归思想。
最后处理第三种情况，那么就要分别求解出 [i, mid) 和 [mid, j）中的连续子序列和，因为第三种情况是分布在 mid 左右，并且是连续的，所以这种情况的连续子序列的和就是 leftMax + rightMax。如下代码所示：
static int maxSubArray(int[] nums, int begin, int end) {
if (end - begin < 2) return nums[begin];
int mid = (begin + end) >> 1;
int leftMax = Integer.MIN_VALUE;
int leftSum = 0;
for (int i = mid-1; i >= begin; i--) {
leftSum += nums[i];
leftMax = Math.max(leftMax, leftSum);
}
int rightMax = Integer.MIN_VALUE;
int rightSum = 0;
for (int i = mid; i < end; i++) {
rightSum += nums[i];
rightMax = Math.max(rightMax, rightSum);
}
return Math.max(leftMax + rightMax,
Math.max(maxSubArray(nums, begin, mid), maxSubArray(nums, mid, end))
);
}
函数中最后的 return 后的代码就是比较这三种情况，并返回其中最大的值。因为是递归的方式，所以函数中一定要有结束递归的条件，if (end - begin < 2) return nums[begin]; 就是递归基。
通过分治策略求连续最大子序列和的空间复杂度是 O( log \log logn)，时间复杂度是 O(n log \log logn)，低于暴力求解的复杂度。
总结
- 分治策略，就是将问题拆分成规模小的子问题，并继续拆分，直到能直接得出答案后再反推导出原问题答案；
- 分治策略更适合使用递归思想；
- 求序列中的最大子序列和，使用分治能降低空间和时间复杂度。