题目

• 输入一个 非空 整型数组，数组里的数可能为正，也可能为负。
• 数组中一个或连续的多个整数组成一个子数组。
• 求所有子数组的和的最大值。
• 要求时间复杂度为 O(n)。
• 数据范围：

数组长度 [0,1000]。

示例

• 示例1

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

代码

解法：dp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN,s = 0;
        for(auto a : nums){
            if(s < 0)   s = 0;
            s += a;
            res = max(res,s);
        }
        return res;
    }
};

代码解析：1、是我刚开始想的太麻烦了，关键在于对 s 的定义
2、s 为以上一个位置结尾的连续子数组的和的最大值

if(s < 0)   s = 0;

3、当 s 小于 0 时，说明前面的值对当前值是副作用，清零即可。

题目：连续子数组的最大和