vvrf / DSA.log

问题拆解

找出数组中和最大的连续子数组，返回它的和。暴力枚举所有子数组是 O(n²)，即便用前缀和优化掉求和的开销，枚举本身还是平方级。

直接定义 dp[i] 为“前 i 个元素的最大子数组和”会发现推不动：dp[i-1] 对应的子数组不知道结束在哪里，没法判断 nums[i] 能不能接上去。换一个定义就通了——dp[i] 表示以 nums[i] 结尾的最大子数组和。结尾固定后，选择只剩一个：nums[i] 要么接在以 nums[i-1] 结尾的子数组后面，要么另起炉灶自己单干。

dp[i] = max(dp[i-1] + nums[i], nums[i])

两者取谁，就看 dp[i-1] 是不是正的：前面攒下的是正资产就带上，是负资产就丢掉。最终答案是所有 dp[i] 里的最大值——最大子数组总得以某个位置结尾。

当“前 i 个的最优解”推不出转移时，试试收紧成“以 i 结尾的最优解”：加强的约束反而让转移变得唯一。

Kadane：滚动成一个变量

dp[i] 只依赖 dp[i-1]，整张表可以压成一个变量 cur，同时用 best 记录历史最大值。

public int maxSubArray(int[] nums) {
    int cur = nums[0];  // 以当前位置结尾的最大和
    int best = nums[0]; // 全局最大
    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(cur + nums[i], nums[i]); // 接上前段 or 另起炉灶
        best = Math.max(best, cur);
    }
    return best;
}

def maxSubArray(nums: list[int]) -> int:
    cur = best = nums[0]  # cur：以当前位置结尾的最大和
    for x in nums[1:]:
        cur = max(cur + x, x)  # 接上前段 or 另起炉灶
        best = max(best, cur)
    return best

func maxSubArray(nums []int) int {
    cur, best := nums[0], nums[0] // cur：以当前位置结尾的最大和
    for _, x := range nums[1:] {
        cur = max(cur+x, x) // 接上前段 or 另起炉灶
        best = max(best, cur)
    }
    return best
}

pub fn max_sub_array(nums: Vec<i32>) -> i32 {
    let mut cur = nums[0]; // 以当前位置结尾的最大和
    let mut best = nums[0];
    for &x in &nums[1..] {
        cur = (cur + x).max(x); // 接上前段 or 另起炉灶
        best = best.max(cur);
    }
    best
}

两个变量的初值都设成 nums[0] 而不是 0——这是本题最常见的错误来源。数组可能全是负数（如 [-3, -1, -2]，答案是 -1），如果 best 初始化为 0，会错误地返回 0，对应了一个题目不允许的“空子数组”。同理，cur = max(cur + x, x) 中的第二个选项是 x 本身而非 0：另起炉灶也必须把当前元素收进来，子数组不能为空。

复杂度

指标	复杂度	原因
时间	`O(n)`	单次遍历，每个元素做一次 max
空间	`O(1)`	dp 数组滚动成两个变量

可以迁移的模式

“最大子数组/子串”类问题的状态定义首选“以 i 结尾”，乘积最大子数组（152）、最长递增子序列（300）同源；
初值和边界要用“全负数组”来自检，凡是不允许空区间的题，0 都不是安全的初值；
转移只依赖前一项的 DP，一律可以滚动成常数空间。

Kadane 算法五行写完，但“换个状态定义让转移成立”这个动作，比代码本身值钱得多。