最大子数组(分治法)
题目
剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode） (leetcode-cn.com)
题解
最大子数组，但是分治法 - 连续子数组的最大和 - 力扣（LeetCode） (leetcode-cn.com)
注意考虑两侧的情况
解题思路
见《算法导论》P70
如果把原数组分成两部分
左:[low,mid] 和右: [mid+1,high]
分别对左右部分求最大子数组
那么就有3种情况
-
左半部分的最大子数组就是原数组的最大子数组
-
右半部分的最大子数组就是原数组的最大子数组
-
原数组的最大子数组跨越了左右两个部分
1 2 两种情况可以直接调用 maxSubArray 递归求解
情况 3 需要进行计算
若最大子数组跨越了左右两部分，那么最大子数组可以表示成
[i,mid] [mid+1,j]
而 [i,mid] 是左半部分以 arr[mid] 为结尾的最大子数组
而 [mid+1,j] 是右半部分以 arr[mid+1] 为开头的最大子数组
代码(golang)
func maxSubArray(nums []int) int {
return maxSubarray(nums,0,len(nums)-1)
}
func maxSubarray(arr []int, low, high int) int {
if low == high {
? return arr[low]
} else {
? mid := (low + high) / 2
? var leftMax, rightMax, crossMax int
? leftMax = maxSubarray(arr, low, mid)
? rightMax = maxSubarray(arr, mid+1, high)
? crossMax = maxCrossingArray(arr, low, mid, high)
? if leftMax >= rightMax && leftMax >= crossMax {
? return leftMax
? } else if rightMax >= leftMax && rightMax >= crossMax {
? return rightMax
? } else {
? return crossMax
? }
}
}
func maxCrossingArray(arr []int, low, mid, high int) int {
var leftSum, rightSum, sum int
var i int
leftSum = int(math.Inf(-1))
rightSum = leftSum
sum = 0
for i = mid; i >= low; i-- {
? sum = sum + arr[i]
? if sum > leftSum {
? leftSum = sum
? }
}
sum = 0
for i = mid + 1; i <= high; i++ {
? sum = sum + arr[i]
? if sum > rightSum {
? rightSum = sum
? }
}
return leftSum + rightSum
}