题目描述

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

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

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

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

样例

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

输出：18

算法

(动态规划)

1. s这个变量中存储的是 以前一个数结尾的子数组中，和最大的是多少
2. 如果s <= 0，那么就将s置为0，因为可能存在负数，不能将负收益的s加进来
3. 如果s > 0，就让s += x。
4. 因为是求最大值，所以res的初值置为 无穷小INT_MIN。同时，每一次迭代，都要更新res，也就是res = max(res, s)。最后返回的res就是 最大值。

时间复杂度

$O(n)$
将nums数组中的所有元素都遍历了一遍，所以是$O(n)$

C++ 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int s = 0;
        int res = INT_MIN;    // **1
        for(auto x : nums)
        {
            if(s <= 0) s = x;
            else s += x;

            res = max(res, s);  // **2
        }

        return res;
    }
};

C++ 简写版本

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int s = 0;
        int res = INT_MIN;    // **1
        for(auto x : nums)
        {
            if(s < 0) s = 0;
            s += x;

            res = max(res, s);  // **2
        }

        return res;
    }
};