89.最大子数组和
题目
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
- 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
- 输出：6
- 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
- 输入：nums = [1]
- 输出：1
示例 3：
- 输入：nums = [5,4,-1,7,8]
- 输出：23
提示：
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
思路
▎ 前面累积的那段和，如果是负数，那它就是拖累 —— 甩掉它，从我这里重新开始。
因为如果 cur[i-1] < 0，那么 cur[i-1] + nums[i] < nums[i]，带着它只会让我变小。反过来只要 cur[i-1] > 0，就是个正资产，接着用。
这就是著名的 Kadane 算法。 一句话概括：
▎ 一路往前加，一旦累积和变成负数，就立刻清零重新开始；过程中随时记录见过的最大值。
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
┌─────┬─────────┬───────────────┬────────────────────────────────────┬──────┐
│ i │ nums[i] │ cur（上一轮） │ cur[i] = max(nums[i], cur+nums[i]) │ best │
├─────┼─────────┼───────────────┼────────────────────────────────────┼──────┤
│ 0 │ -2 │ — │ -2（起点） │ -2 │
├─────┼─────────┼───────────────┼────────────────────────────────────┼──────┤
│ 1 │ 1 │ -2 │ max(1, -1) = 1 ← 甩掉负累积 │ 1 │
├─────┼─────────┼───────────────┼────────────────────────────────────┼──────┤
│ 2 │ -3 │ 1 │ max(-3, -2) = -2 │ 1 │
├─────┼─────────┼───────────────┼────────────────────────────────────┼──────┤
│ 3 │ 4 │ -2 │ max(4, 2) = 4 ← 又甩掉一次 │ 4 │
├─────┼─────────┼───────────────┼────────────────────────────────────┼──────┤
│ 4 │ -1 │ 4 │ max(-1, 3) = 3 │ 4 │
├─────┼─────────┼───────────────┼────────────────────────────────────┼──────┤
│ 5 │ 2 │ 3 │ max(2, 5) = 5 │ 5 │
├─────┼─────────┼───────────────┼────────────────────────────────────┼──────┤
│ 6 │ 1 │ 5 │ max(1, 6) = 6 │ 6 ✅ │
├─────┼─────────┼───────────────┼────────────────────────────────────┼──────┤
│ 7 │ -5 │ 6 │ max(-5, 1) = 1 │ 6 │
├─────┼─────────┼───────────────┼────────────────────────────────────┼──────┤
│ 8 │ 4 │ 1 │ max(4, 5) = 5 │ 6 │
└─────┴─────────┴───────────────┴────────────────────────────────────┴──────┘
答案 6。
class Solution {
/**
* 最大子数组和 —— Kadane 算法
*
* 核心思想：固定右端点，问"以 i 结尾的最大子数组和是多少"。
* 答案只有两种：从 i 重新开始，或者接着前面那段继续。
* 等价于：前面累积的和是负数就甩掉，是正数就继续用。
*
* 时间复杂度 O(n)：只扫一遍
* 空间复杂度 O(1)：只用两个变量
*/
fun maxSubArray(nums: IntArray): Int {
// cur = 以当前元素结尾的最大子数组和
// best = 目前为止见过的全局最大值
// ⚠️ 两者都必须初始化为 nums[0]，不能是 0！
// 子数组不能为空，全负数数组的答案是那个最大的负数
var cur = nums[0]
var best = nums[0]
// 从下标 1 开始，因为 0 已经作为初值处理过了
for (i in 1 until nums.size) {
// 决策：接着前面那段继续，还是从我这里重新开一段？
// 若 cur < 0，cur + nums[i] 必然小于 nums[i] → 自动选择重开
cur = maxOf(nums[i], cur + nums[i])
// cur 会起落，best 只记录历史最高水位
best = maxOf(best, cur)
}
return best
}
}
核心就两行。写完拿 [-1] 和 [-2, -1] 试一下，这两个用例能立刻验出初始化是否写错。
LeetCode 这题的进阶问题是：
▎ 你能设计一个时间复杂度为 O(n log n) 的解法吗？
比 O(n) 还慢，为什么要学？因为分治的结构能被改造成线段树，从而支持"任意区间查询最大子数组和"这种动态问题——那是 Kadane 做不到的。
分治思路： 把数组从中间劈开，最大子数组只有三种可能的位置：
[ 左半 | 右半 ] ① ② └─── ③ ────┘ 跨越中点
- ① 完全在左半 → 递归求解
- ② 完全在右半 → 递归求解
- ③ 跨越中点 → 必然包含 mid 和 mid+1，所以从中点向左扫出最大后缀和，向右扫出最大前缀和，两者相加
三者取最大即可。
class Solution3 {
/**
* 分治法（题目 Follow-up）
*
* 时间复杂度 O(n log n)：递归 log n 层，每层跨中点扫描共 O(n)
* 空间复杂度 O(log n)：递归栈
*/
fun maxSubArray(nums: IntArray): Int = divide(nums, 0, nums.size - 1)
private fun divide(nums: IntArray, lo: Int, hi: Int): Int {
// 只剩一个元素，它自己就是答案
if (lo == hi) return nums[lo]
val mid = lo + (hi - lo) / 2
// ① 完全落在左半 / ② 完全落在右半
val leftBest = divide(nums, lo, mid)
val rightBest = divide(nums, mid + 1, hi)
// ③ 跨越中点：必须同时包含 mid 和 mid+1
// 从 mid 向左累加，取途中最大值 → 最大后缀和
var sum = 0
var maxSuffix = Int.MIN_VALUE
for (i in mid downTo lo) {
sum += nums[i]
maxSuffix = maxOf(maxSuffix, sum)
}
// 从 mid+1 向右累加，取途中最大值 → 最大前缀和
sum = 0
var maxPrefix = Int.MIN_VALUE
for (i in mid + 1..hi) {
sum += nums[i]
maxPrefix = maxOf(maxPrefix, sum)
}
// 三种情况取最大
return maxOf(leftBest, rightBest, maxSuffix + maxPrefix)
}
}
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(1)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!