53. 最大子数组和

考点

• 最大子数组和

思路

一、问题描述

给定一个整数数组 \[ \texttt{nums} = [a_0, a_1, \dots, a_{n-1}] \] 要求在所有连续子数组中，找到元素和最大的那一个，并返回该最大和。

---

二、算法思想概述

该问题可以使用动态规划（Dynamic Programming）求解。核心思想是：

对于每一个位置，考虑“以该位置结尾的最大子数组和”。

是否要把当前位置的元素接在前面的子数组后面，取决于前一个位置的最优结果是否为正。

---

三、状态定义

定义状态： \[ dp[i] = \text{以 } a_i \text{ 结尾的连续子数组的最大和} \] 注意：

• 必须以 \(a_i\) 作为结尾
• 子数组不能为空

---

四、状态转移方程

对于位置 \(i \ge 1\)，有两种选择：

1. 单独从当前位置重新开始 \[ dp[i] = a_i \]

2. 将当前位置接在前一个子数组之后 \[ dp[i] = dp[i-1] + a_i \]

因此状态转移方程为： \[ dp[i] = \max\bigl(a_i,\; dp[i-1] + a_i\bigr) \] 该公式的含义是：

• 如果前面的子数组和为负数，则舍弃，重新开始
• 如果前面的子数组和为正数，则继续累加

---

五、初始值的设定（关键点）

由于子数组不能为空，初始状态必须来自数组本身： \[ dp[0] = a_0 \] 同时，最终答案也至少为第一个元素： \[ ans = a_0 \] 这一步非常重要，尤其在数组全为负数的情况下，能够保证结果正确。

---

六、答案的确定方式

最大子数组和不一定以最后一个元素结尾，因此需要在遍历过程中维护全局最大值： \[ ans = \max_{0 \le i < n} dp[i] \] 在实现中，可以在每次计算 \(dp[i]\) 后，实时更新答案。

---

七、空间优化（实现层面）

由于状态转移只依赖于前一个状态 \(dp[i-1]\)，可以用一个变量代替数组：

• pre：表示 \(dp[i-1]\)
• cur：表示当前的 \(dp[i]\)

---

八、算法流程总结

1. 初始化：

   • pre = nums[0]
   • ans = nums[0]

2. 从左到右遍历数组：

   • 计算当前状态 \[ cur = \max(nums[i],\; pre + nums[i]) \]

   • 更新答案 \[ ans = \max(ans,\; cur) \]

   • 更新 pre = cur

3. 返回 ans

---

九、时间与空间复杂度分析

• 时间复杂度： \[ O(n) \] 只需一次线性扫描

• 空间复杂度： \[ O(1) \] 仅使用常数个变量

---

十、算法本质总结

该算法本质上是一种：

以当前位置为结尾的最优子结构动态规划

其核心判断是：

“前缀是否值得被保留”

这也是该问题被称为 Kadane 算法 的原因所在。

---

十一、AC代码

class Solution {
public:
    static const int maxn = 1e5 + 5;
    int maxSubArray(vector<int>& nums) {
        int res = nums[0], pre = nums[0], cur;
        for (int i = 1; i < nums.size(); ++i) {
            cur = max(nums[i], pre + nums[i]), res = max(res, cur), pre = cur;
        }
        return res;
    }
};