53. 最大子数组和

难度：🟡 Medium | 标签：动归、Kadane | 状态：⬜ LeetCode 链接

思路

Kadane 算法。维护「以 i 结尾」的最大子数组和 cur：

• 选择继续累加 cur + x 还是另起炉灶 x：取大
• 全局答案 best 单独维护

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur = nums[0], best = nums[0];
        for (int i = 1; i < (int)nums.size(); ++i) {
            cur = max(nums[i], cur + nums[i]);
            best = max(best, cur);
        }
        return best;
    }
};

复杂度

• 时间 O(n)，空间 O(1)
• 分治解法 O(n log n)，仅作扩展了解

易错 / 回顾

• 全负数时答案是最大负数，不是 0
• 初始 cur 和 best 都从 nums[0] 起，循环从 1 开始
• 变种：求子数组本身（不只是和） → 记 start/end