最大子数组和（Maximum Subarray）
📌 定义
最大子数组和问题是指：给定一个整数数组，找到一个具有最大和的连续子数组（至少包含一个元素），返回其最大和。
数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
最大子数组: [4, -1, 2, 1]
最大和: 6
🎯 解法对比
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(n³) | O(1) | 三层循环 |
| 优化枚举 | O(n²) | O(1) | 两层循环+累加 |
| 分治法 | O(n log n) | O(log n) | 本文重点 |
| 动态规划 | O(n) | O(1) | 最优解 |
💡 分治法核心思想
将数组从中间分成左右两部分，最大子数组和只可能出现在三种情况：
- 左半部分：完全在左边
- 右半部分：完全在右边
- 跨越中点：横跨左右两边
数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
↑
中点
情况1: 左半部分最大和 = 1
情况2: 右半部分最大和 = 6 ([4,-1,2,1])
情况3: 跨越中点最大和 = 5 ([4,-1,2,1])
取最大值 = 6
Go 代码
Go 实现
package main
import (
"fmt"
"math"
)
func maxSubArrayDivide(nums []int) int {
return helper(nums, 0, len(nums)-1)
}
func helper(nums []int, left, right int) int {
if left == right {
return nums[left]
}
mid := (left + right) / 2
leftMax := helper(nums, left, mid)
rightMax := helper(nums, mid+1, right)
crossMax := crossSum(nums, left, right, mid)
return max(leftMax, max(rightMax, crossMax))
}
func crossSum(nums []int, left, right, mid int) int {
leftSum := math.MinInt32
currSum := 0
for i := mid; i >= left; i-- {
currSum += nums[i]
if currSum > leftSum {
leftSum = currSum
}
}
rightSum := math.MinInt32
currSum = 0
for i := mid + 1; i <= right; i++ {
currSum += nums[i]
if currSum > rightSum {
rightSum = currSum
}
}
return leftSum + rightSum
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
fmt.Printf("最大子数组和: %d\n", maxSubArrayDivide(nums))
}思路展开
分治法的递归树
原数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
[-2,1,-3,4,-1,2,1,-5,4]
/ \
[-2,1,-3,4,-1] [2,1,-5,4]
/ \ / \
[-2,1,-3] [4,-1] [2,1] [-5,4]
/ \ / \ / \ / \
[-2,1] [-3] [4] [-1] [2] [1] [-5] [4]
/ \
[-2][1]
深度：O(log n)
每层时间：O(n)
总时间：O(n log n)
跨越中点的计算
数组: [4, -1, 2, 1]
中点: 在-1和2之间
从中点向左: 4, -1 → 左边最大和 = 4 + (-1) = 3
从中点向右: 2, 1 → 右边最大和 = 2 + 1 = 3
跨越中点的最大和 = 3 + 3 = 6
经典题目
基础应用
变体
2D扩展
- 最大子矩阵和
- 最大正方形
⚖️ 优缺点
分治法
优点：
- ✅ 展示分治思想
- ✅ 可扩展到2D问题
缺点：
- ❌ 时间复杂度O(n log n)不是最优
- ❌ 需要额外的栈空间
动态规划（Kadane算法）
优点：
- ✅ 时间复杂度O(n)
- ✅ 空间复杂度O(1)
- ✅ 代码简洁
缺点：
- ❌ 不易扩展到2D
🎨 应用场景
- 股票交易：找最佳买卖时机
- 图像处理：找最亮区域
- 信号处理：找最强信号段
- 数据分析：找最优时间窗口