在上一篇文章中，我们介绍了贪婪策略，接下来我们将要探索分治策略。分治就是分而治之，它的一般步骤是
- 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
网友评论