创造算法的算法：分治法

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

学习算法是为了用程序的思想，抽象实际问题，提供方便的解决方案。

分治法是编程界排名前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. 找到小问题的解决方案。

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

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

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

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