yicong@algo: ~/code/05-array/0053-maximum-subarray.cpp

yicong@algo:~/code/05-array$ cat 0053-maximum-subarray.cpp

53. 最大子数组和

中等 普通数组 题目 ↗ 源码 ↗

// 思路

Kadane 动态规划,cur 表示以当前元素结尾的最大和 设 curSum = "以当前下标 i 结尾"的最大子数组和,那么: 要么 nums[i] 单独成段: curSum = nums[i] 要么接在前一个的后面: curSum = 前一个的 curSum + nums[i] 取两者较大值即可。为什么只看这两种?因为任何以 i 结尾的子数组 去掉 nums[i] 之后,要么是空的(单独成段),要么是以 i-1 结尾的某个子数组。 而要让"加上 nums[i] 之后"最大,那前面的那段自然也要取最大的, 所以"以 i-1 结尾的最大和"就够用了,这就是最优子结构。 全程只需要滚动两个变量,所以空间 O(1)。 版本一:Kadane,O(n) 时间 / O(1) 空间,标准答案。 版本二:分治,O(n log n),面试有时会追问"不用 DP 怎么做",或者"数据太大要并行"。 分治的好处是可并行、可处理流式拼接,缺点是常数大、代码长。

// 时间复杂度

版本一:O(n),一趟扫描 版本二:O(n log n),T(n) = 2T(n/2) + O(n)

// 空间复杂度

版本一:O(1),只有 curSum 和 maxSum 两个变量 版本二:O(log n),递归栈深度

// 易错点

全负数时答案不是 0,cur 要初始化为 nums[0] 或 -INF 1. 两个变量都必须初始化为 nums[0],不能初始化为 0。 如果写成 0,遇到 [-3,-1,-2] 会返回 0,正确答案是 -1。 2. curSum 的含义是"以当前元素结尾",不是"当前最优"。别把两者搞混: 当前最优可能存在 maxSum 里,而 curSum 允许是负数(因为后面可能翻盘)。 3. 更新顺序不能反:先更新 curSum,再用新的 curSum 更新 maxSum。 4. 版本二里"跨中点"的那部分必须至少包含 nums[mid] 和 nums[mid+1], 否则会退化成单侧,和左右递归的结果重复计算。

// 面试口述要点

1. 先说暴力:枚举左右端点再求和,O(n³);用前缀和降到 O(n²); 2. 再给最优子结构:curSum(i) = max(nums[i], curSum(i-1) + nums[i]), "接上前面"或"从自己重新开始",二选一,一趟扫完 O(n); 3. 主动说出全负数的坑:初始化为 nums[0] 而不是 0,这是最常见的 WA; 4. 如果被追问"还有别的方法吗",给分治:最大值只有三种可能—— 完全在左半、完全在右半、跨过中点,第三种用"以 mid 结尾的最大后缀 + 以 mid+1 开头的最大前缀"算出,总复杂度 O(n log n)。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // ================================================================
    // 版本一:Kadane(动态规划 + 滚动变量),O(n) 时间 / O(1) 空间
    //   curSum : 以当前下标结尾的最大子数组和
    //   maxSum : 目前为止见过的最优答案
    // ================================================================
    int maxSubArray(vector<int>& nums) {
        int n = (int)nums.size();

        // 注意:初始化为 nums[0],不是 0
        int curSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < n; i++) {
            // 二选一:接上前面的,或者从 nums[i] 重新开始
            curSum = max(nums[i], curSum + nums[i]);

            // 先更新完 curSum,再用它更新 maxSum
            maxSum = max(maxSum, curSum);
        }

        return maxSum;
    }

    // ================================================================
    // 版本二:分治,O(n log n)
    //   区间 [left, right] 上的最大子数组和只有三种可能:
    //     1) 完全在左半边 [left, mid];
    //     2) 完全在右半边 [mid+1, right];
    //     3) 跨过中点:必须以 nums[mid] 结尾的一段 + 必须以 nums[mid+1] 开头的一段。
    //   前两种递归,第三种在 O(right-left+1) 内扫出来。
    // ================================================================
    int maxSubArray_v2(vector<int>& nums) {
        return solve(nums, 0, (int)nums.size() - 1);
    }

private:
    int solve(vector<int>& nums, int left, int right) {
        if (left == right) {                         // 只有一个数,只能是它自己
            return nums[left];
        }

        int mid = left + (right - left) / 2;         // 这样写避免 left+right 溢出

        // ---------- 情形 1 和 2:完全在某一侧 ----------
        int bestLeft = solve(nums, left, mid);
        int bestRight = solve(nums, mid + 1, right);

        // ---------- 情形 3:跨过中点 ----------
        // 左半边:必须以 nums[mid] 结尾,往左扩展取最大
        int leftPart = nums[mid];
        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftPart = max(leftPart, sum);
        }

        // 右半边:必须以 nums[mid+1] 开头,往右扩展取最大
        int rightPart = nums[mid + 1];
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightPart = max(rightPart, sum);
        }

        int bestCross = leftPart + rightPart;

        // ---------- 三种情况取最大 ----------
        return max(max(bestLeft, bestRight), bestCross);
    }
};

// 本地测试:输入 n,然后 n 个整数;输出最大子数组和
// 同时跑两个版本并比对结果,方便验证优化版和原版等价
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<int> nums(n);
    for (int& x : nums) cin >> x;

    int ans1 = Solution().maxSubArray(nums);
    int ans2 = Solution().maxSubArray_v2(nums);

    if (ans1 != ans2) {
        cout << "MISMATCH: v1=" << ans1 << " v2=" << ans2 << '\n';
        return 0;
    }
    cout << ans1 << '\n';
    return 0;
}