分治算法
最近看到《算法導論》的分治策略一節(jié)竹宋，看到的一個題目可以優(yōu)化引申出來多種解法石蔗，同時也可以幫助理解分治策略的化整為零和動態(tài)規(guī)劃的動態(tài)轉移方程的思維杰赛。
最大子數(shù)組問題
最大子數(shù)組：數(shù)組 A 中的和最大的非空連續(xù)子數(shù)組顽腾。
暴力解法 O(n^2)
這個問題可以用暴力解法蓄髓，兩層循環(huán)遍歷汪茧，時間復雜度為 O(n^2)裂垦，當然最容易想到的并不是最好的解法葡秒。
package main
import (
"fmt"
)
func main() {
A := []int{13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}
left, right, sum := FindMaxSubArray(A)
fmt.Println(left, right, sum)
}
func FindMaxSubArray(A []int) (left, right, sum int){
// 這里先不考慮 max 取值的問題魔招，可以取切片的第一個元素或者 int 的最小值晰搀。
var max int
for i := 0; i < len(A); i++ {
sum = 0
for j := i; j < len(A); j++ {
sum += A[j]
if sum > max {
max = sum
left, right = i, j
}
}
}
return left, right, sum
}
可以得知最大的和為 43，即下標 7, 10 之間的子數(shù)組办斑。
分治解法 O(nlgn)
既然這一節(jié)是講分治策略外恕，那么怎么用分治的思想來優(yōu)化呢。這個解法確實比較難懂乡翅，如果讓腦袋去跑一遍遞歸鳞疲，真的有點累。那么分治本來就是一種局部整體的思想蠕蚜，我們把切片分成三組尚洽，左，中靶累，右腺毫。那么我們只需要得出，這三個子集的最大值即可挣柬。然后再不斷分化下去潮酒，最后把最大值冒上來。分治解法的關鍵就是如何用整體局部的思想把問題抽象化邪蛔。
image.png
func FindMaxCrossingSubArray(A []int, low, mid, high int) (int, int, int){
// 這個函數(shù)為什么從中間分開算呢急黎？因為得出的結果必須要跟 mid 位相關
var maxLeft, maxRight int
// 取負無窮大就行，這里簡化處理
leftSum := -99999
sum := 0
for i := mid; i >= low; i-- {
sum += A[i]
if sum > leftSum {
leftSum = sum
maxLeft = i
}
}
rightSum := -99999
sum = 0
for j := mid + 1; j <= high; j++ {
sum += A[j]
if sum > rightSum {
rightSum = sum
maxRight = j
}
}
return maxLeft, maxRight, leftSum+rightSum
}
func FindMaxSubArray(A []int, low, high int) (int, int, int) {
if low == high {
return low, high, A[low]
} else {
mid := (low + high) >> 1
// 求左半?yún)^(qū)子數(shù)組最大值
leftLow, leftHigh, leftSum := FindMaxSubArray(A, low, mid)
// 求右半?yún)^(qū)子數(shù)組最大值
rightLow, rightHigh, rightSum := FindMaxSubArray(A, mid+1, high)
// 求包含中位數(shù)區(qū)子數(shù)組的最大值
crossLow, crossHigh, crossSum := FindMaxCrossingSubArray(A, low, mid, high)
if leftSum >= rightSum && leftSum >= crossSum {
return leftLow, leftHigh, leftSum
} else if rightSum >= leftSum && rightSum >= crossSum {
return rightLow, rightHigh, rightSum
} else {
return crossLow, crossHigh, crossSum
}
}
}
可以將時間復雜度降低到 O(n) 嗎？ 動態(tài)規(guī)劃叁熔。
線性解法 O(n)
從題目上看委乌，可以發(fā)現(xiàn)這道題滿足動態(tài)規(guī)劃的思想∪倩兀可以求得動態(tài)轉移方程為：F(n) = max(F(n-1)+A[n], A[n])
func FindMaxSubArray(nums []int) (left, right, maxNum int) {
var isLeftMax bool
maxNum = nums[0]
v := make([]int, len(nums))
v[0] = nums[0]
for i := 1; i < len(nums); i++ {
v[i], isLeftMax = max(nums[i], v[i-1] + nums[i])
if isLeftMax {
left = i
}
if v[i] > maxNum {
maxNum = v[i]
right = i
}
}
return left, right, maxNum
}
func max(a, b int) (int, bool) {
if a > b {
return a, true
}
return b, false
}
