题目描述

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为 O(n)。

样例

输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

算法

(动态规划) $O(n)$

状态表示：s，表示以前一个数结尾的子数组中和最大是多少
状态计算：

1. 用变量 res 存储所有子数组中的最大和，枚举 nums，假设每个数是 x
2. 如果 s <= 0，那么由当前数 x 构成的子数组就是和最大的，所以从当前数开始计算 s s = x
3. 如果 s > 0，那么将当前数 x 加上，计算以当前数 x 结尾的子数组最大和 s += x
4. 每次计算完 s，更新 res

时间复杂度

遍历一遍数组，所以时间复杂度为 $O(n)$

C++ 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // res 答案，s 表示以前一个数结尾的子数组中和最大是多少
        int res = INT_MIN, s = 0;
        for (auto x : nums)
        {
            if (s <= 0) s = x;
            else s += x;
            res = max(res, s);
        }
        return res;
    }
};

C++ 代码（精简版）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // res 答案，s 表示以前一个数结尾的子数组中和最大是多少
        int res = INT_MIN, s = 0;
        for (auto x : nums)
        {
            if (s < 0) s = 0;
            s += x;
            res = max(res, s);
        }
        return res;
    }
};