创造算法的算法：分治法

有多少人学习算法时，都是从排序入手，而后就没有而后了，不是算法有多难，而是算法对程序员来说，有点相似武侠世界里的内功心法，练了半天，总觉得与功夫招式没什么大关系，和工作遇到的问题关系也不是那么直接，实际上，基本上所有语言都内置了排序的方法，有多少人会自己写个快排去排序的？！
那么学习算法究竟有什么用呢？这里我提供一个角度：

学习算法是为了用程序的思想，笼统实际问题，提供方便的处理方案。

分治法是编程界排名前5的重要算法之一，但是它本身并不是一种具体的算法，也没有典型的数据结构，我们先从一个例子来看下它能处理什么样的问题：
《最大子序和》：
给定一个整数数组 nums ，找到一个具备最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

分治法.001

问题中，最终的结果当然是9个数字中的最大值，问题是，9个数字的子数组有多少呢？可以2两个一组、3个一组，4个一组，这样写算法必然繁琐复杂，要想办法简化一下问题，先把9个数字分成两部分：

分治法.002

假设我们已经求出了[-2…-5]部分的最大值，记为sumMax(0…7)，问题就简单了，只要在sumMax(0…7)、4、sumMax(0…7)+4 三者之间取最大值就可。

剩下的你可能已经知道了，[-2…-5]部分也需要求最大和，一样分为两部分，这样一直分下去：

分治法.003

最后会发现，只剩下 -2 和 1，这时，只要要比较 （-2 + 1）和 1 的大小，显然取1，这是为了满足题目中“连续子数组”的要求，靠右边的数代表所在组，才能参加更大分组的计算。

由分析可见，用递归可以很方便的实现，只要要将去掉末尾的数组再次调用相同方法就可，因为取子数组很耗费计算时，这里开展为循环，下面完整算法（Swift形容）：

func maxSubArray(_ nums: [Int]) -> Int {        var maxAll:Int = 0        if (nums.count == 0) {            maxAll = 0            return 0        }        if (nums.count == 1) {            maxAll = nums[0]            return nums[0]        }        maxAll = nums[0]        var subSumMax = 0        if (nums.count >= 2) {            for v in nums {                subSumMax += v                subSumMax = max(subSumMax, v)                maxAll = max(subSumMax, maxAll)            }        }        return maxAll    }

maxAll 用来记录曾经达到过的最大和。
通过以上的详细分析，可以总结出，分治法包括两个步骤：

1. 将大问题分拆成小问题。
2. 找到小问题的处理方案。

以上过程是个互动过程，有时需要尝试不同的分拆方法，关键看分拆的小问题能否有一致的处理方案。

在众多算法中，很多都是分治法的具体实践：

• 二分查找
• 归并排序
• 快速排序

当你领悟了分治法的思想后，很多算法都可以自行推导得出，现在是不是对学好算法更有信心了呢？欢迎你的留言，我们一同修炼心法。