题目描述

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

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

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

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

数据范围
数组长度 [1,1000]
。
数组内元素取值范围 [−200,200]
。

样例

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

输出：18

算法

每次更新只考虑第i个数和前i-1个数的关系

• presum表示前i-1个数构成的子数组和的最大值
• 如果 presum > 0 ，那么用presum + nums[i]更新第i个数的presum
• 如果 presum <= 0，那么nums[i]往后的子数组最大值不能再带上前i-1个数了，应该用nums[i]更新presum。因为再怎么划分，前i-1个数最大和总是小于零，“拖后腿”

用res记录所有presum的最大值

时间复杂度 $O(n)$

参考文献

y总视频讲解

C++ 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int presum = 0;
        for(int i = 0; i< nums.size(); i++){
            if(presum > 0) presum = presum + nums[i];
            else presum = nums[i];
            res = max(res, presum);
        }
        return res;
    }
};