分析

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

---

题解

朴素动态规划

核心思想：

1. DP 状态定义 dp[i]：以 下标 i 结尾 的连续子数组的最大和。 关键点：必须以 i 结尾，保证连续性。

2. 状态转移方程（核心公式） $dp[i] = \max(nums[i],\ dp[i-1] + nums[i])$ 两种选择：

• 舍弃前面：子数组从当前元素重新开始，取 nums[i]

• 接上前面：把当前元素拼接到前一个最优子数组后，取 dp[i-1] + nums[i]

全局答案：遍历所有dp[i] 取最大值。

代码

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

时间复杂度：$O(n)$ 空间复杂度：$O(n)$

最优解：Kadane 贪心 DP（空间优化）

优化思路

观察 DP 方程：dp[i] 只依赖 dp[i-1]，不需要存整个数组。

用单个变量滚动替换 dp 数组：

• curSum：替代 dp[i]，当前结尾的最大子数组和

• maxSum：全局最大值

代码

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

时间复杂度：$O(n)$ 空间复杂度：$O(1)$

拓展解法：分治算法

分治核心思想

最大子数组只存在三种情况：

1. 完全在左半区间

2. 完全在右半区间

3. 跨越中点（左后缀 + 右前缀）

递归求解左右最大值，再计算跨中点最大值，三者取最大。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return divide(nums, 0, nums.size()-1);
    }

    int divide(vector<int>& nums, int l, int r){
        if(l == r) return nums[l];
        int mid = l + (r - l) / 2;
        int leftMax = divide(nums, l, mid);
        int rightMax = divide(nums, mid+1, r);
        int crossMax = getCross(nums, l, mid, r);
        return max({leftMax, rightMax, crossMax});
    }

    int getCross(vector<int>& nums, int l, int mid, int r){
        int leftSum = 0, leftMaxSum = INT_MIN;
        for(int i = mid; i >= l; i--){
            leftSum += nums[i];
            leftMaxSum = max(leftMaxSum, leftSum);
        }
        int rightSum = 0, rightMaxSum = INT_MIN;
        for(int i = mid+1; i <= r; i++){
            rightSum += nums[i];
            rightMaxSum = max(rightMaxSum, rightSum);
        }
        return leftMaxSum + rightMaxSum;
    }
};

补充：

$crossMax = \Bigl(\max_{k\in[l,mid]}\sum_{i=k}^{mid}nums[i]\Bigr) +\Bigl(\max_{k\in[mid+1,r]}\sum_{i=mid+1}^{k}nums[i]\Bigr)$

• 第一部分：$[l,mid]$ 内以 mid 结尾的最大后缀和
• 第二部分：$[mid+1,r]$ 内以 mid+1 开头的最大前缀和

时间复杂度：$O(nlogn)$ 空间复杂度：$O(logn)$，递归栈

三种算法对比总结

算法	时间复杂度	空间复杂度	适用场景
朴素 DP	O(n)	O(n)	教学理解
Kadane（优化DP）	O(n)	O(1)	刷题、面试最优解
分治	O(nlogn)	O(logn)	面试拓展、思维考察

53. 最大子数组和 - 力扣（LeetCode）