分治(Divide And Conquer)

在上一篇文章中，我们介绍了贪婪策略，接下来我们将要探索分治策略。分治就是分而治之，它的一般步骤是

• 1，将原问题分解成若干个规模较小的子问题(子问题和原问题的结构一样，只是规模不一样)。
• 2，子问题又不断分解成规模更小的子问题，直到不能在分解（直到可以轻易计算出子问题的解）
• 3，利用子问题的解推导出原问题的解。
  从上面的步骤中，我们可以看出分治策略非常适合用递归。

DivideAndConquer1.png

下面我们通过一个示例来探索该策略。

分析

Q1:给定一个长度为n的整数序列，求它的最大连续子序列和。

• 比如 -2，-1， -3， 4，-1，2，1，-5，4的最大连续子序列和是 4 + (-1) + 2 + 1 = 6

解法1: 穷举出所有子自序列，分别计算子序列的和，取它们的最大值。

解法1实现

    static func maxSubArrayOne(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 0
        }
        var maxTotalNum = Int.min  // 1

        for(beginIndex, _) in nums.enumerated() { // 2
            for (endIndex, _) in nums.enumerated().filter({ return $0.0 > beginIndex }) { // 3

                var tmpMaxNum = 0
                for index in beginIndex...endIndex { // 4
                    tmpMaxNum += nums[index]
                }
                if maxTotalNum < tmpMaxNum { // 5
                    maxTotalNum = tmpMaxNum
                }
            }
        }
        return maxTotalNum
    }

• 1，将初始最小子序列和设置为最小整数。
• 2，遍历数组，将索引 0 至 索引 count - 1 设置为数组的 beginIndex
• 3，遍历数组，将大于beginIndex的索引值依次作为 endIndex
• 4，取出子序列 [beginIndex endIndex]，算出来该子序列的序列和。
• 5，通过比较，获取子序列和和上一次循环得到子序列和的最大值。

该思路的空间复杂度为 O(1) ,时间复杂度为 O(n ^ 3)
在上面的解法中，我们存在一些重复计算：

 var tmpMaxNum = 0
 for index in beginIndex...endIndex { // 4
        tmpMaxNum += nums[index]
 }

当endIndex变化时，我们都需要遍历数组，来计算其子序列和，但在求[beginIndex endIndex - 1]时，我们就已经计算出该区间的子序列和了，所以，我们可以将其优化一下：

    static func maxSubArrayTwo(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 0
        }
        var maxTotalNum = Int.min

        for(beginIndex, _) in nums.enumerated() {
            var subTotal = 0
            for (endIndex, _) in nums.enumerated().filter({ return $0.0 > beginIndex }) {
                subTotal += nums[endIndex]
                maxTotalNum =  max(maxTotalNum, subTotal)
            }
        }
        return maxTotalNum
    }

通过上面优化，我们减少了一次遍历，这样时间复杂度为O(n ^ 2)

解法2:采用分治的策略，将序列均匀地分割成2个子序列
分割成2部分：

• [begin, end) = [begin, mid) + [mid, end), mid = (begin + end) / 2

假设[begin, end)的最大连续子序列和是 [i , j)，那么它有 3 种可能

• [i，j)存在于 [begin, mid)中，即 begin ≤ i < j < mid, 同时[i , j)也是 [begin, end)的最大连续子序列和。
• [i，j)存在于 [mid, end)中，即 mid ≤ i < j < end, 同时[i , j)也是 [mid, end)的最大连续子序列和。
• [i，j)一部分存在[begin, mid) 中，另一部分存在于[mid, end) 中
  1,[i，j) =[i，mid) + [mid, j)
  2,[i，mid) = [k, mid), begin ≤ k < mid，[k, mid)，也是左边序列的最大子序列和
  3,[mid, j) = [mid, h), mid < k ≤ end， [mid，h)，也是右边序列的最大子序列和

实现

    static func maxSubArrayThree(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 0
        }

        return maxSubArray(nums, 0, nums.count)
    }

    private static func maxSubArray(_ nums:[Int], _ begin: Int, _ end: Int)  -> Int{
        if (end - begin < 2) {
            return nums[begin]
        }


        let mid = (begin + end) >> 1

        // 最大子序列和一部分在左边序列，一部分在右边序列的情况
        // 1:计算右半部分最大连续子序列和
        var rightMax = nums[mid]
        var rightSum = rightMax
        for i in mid..<end {
            rightSum += nums[i]
            rightMax = max(rightSum, rightMax)
        }

        // 2，计算左半部分最大连续子序列和
        var leftMax = nums[mid - 1]
        var leftSum = leftMax
        for i in (begin..<(mid - 1)).reversed() {
            leftSum += nums[i]
            leftMax = max(leftSum, leftMax)
        }
        let maxSubOne = leftMax + rightMax

        // 最大连续子序列和，序列都在左边的情况
        let maxSubTwo = maxSubArray(nums, begin, mid)
        // 最大连续子序列和，序列都在右边的情况
        let maxSubThree = maxSubArray(nums, mid, end)
        return max(max(maxSubTwo,maxSubThree)
            , maxSubOne)
    }

最后附上本文的相关代码DataAndAlgorim