🍥

Hang Zhang

genius.

Data Structure and Algorithm

maxSubArray

53. 最大子数组和

分析

定义状态：
- 用变量 last 表示以当前元素结尾的最大子数组和
- 用变量 res 表示全局最大子数组和
状态转移方程：
- 对于每个元素 num，当前的 last 值可以由以下两种情况决定：
  - 单独包含当前元素：如果此前的 last 为负数，则舍弃
  - 包含当前元素并延续之前的子数组：如果此前的 last 为正数，则将当前元素加入子数组
- 状态转移方程：last = max(num, last + num)
更新全局最大值：
- 在遍历每个元素后，更新全局最大值 res 为：res = max(res, last)

时间复杂度

单次遍历：仅需遍历数组一次，时间复杂度为 O(n)

空间复杂度

只使用了 res 和 last 两个变量，空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution
{
public:
    int maxSubArray(vector<int>& nums)
    {
        int res = INT_MIN; // 全局最大子数组和
        int last = 0;      // 当前子数组和
        for (int num : nums)
        {
            last = std::max(num, last + num); // 动态更新以当前元素结尾的最大子数组和
            res = std::max(res, last);       // 更新全局最大值
        }
        return res;
    }
};