解题思路

此题可以用动态规划解决。
题目要求返回具有最大和的连续子数组的最大和，朴素思路是枚举所有连续子数组并计算其和，返回最大值，但是这样会超时。
我们换个思路，假设f(i)为以nums[i]结尾的连续子数组的最大和，那么f(i)(其中，0≤i<nums.size())中的最大值就是题目的答案。怎么求f(i)呢？注意到，如果已知f(i-1)<0，那么显然f(i)就等于nums[i]，因为如果加上f(i)，还不如就取nums[i]作为以nums[i]结尾的连续子数组和大。而当f(i-1)≥0时，f(i)=f(i-1)+nums[i]。仔细思考这一点，因为题目要求的是连续，连续子数组，而f(i)是指以nums[i]结尾的连续子数组的最大和，注意连续，结尾两个词。
简化一下，则f(i)=max(f(i-1)+nums[i],nums[i])。于是我们想到动态规划方法，可以使用数组dp[n]存储每个f(i)，其中n为nums大小，于是有dp[i] = max(dp[i-1]+nums[i], nums[i])。对数组遍历一遍，再求其中的最大值，就可以得到题目的答案。又由于每个dp[i]只跟前一个f(i)相关，于是dp[n]的空间也可以省了，使用pre记录每一个f(i)的前一项f(i-1)，并不断更新最大和maxSum，遍历完就能得到最大的maxSum。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int m = nums.size();//数组长度
        int pre = -1;//初始化pre为-1
        int maxSum = nums[0];//初始化maxSum为f(0)，即dp[0]，也即nums[0]
        for(int num : nums){//遍历数组，不断更新pre和maxSum
            pre = (max(num, pre+num));
            maxSum = max(maxSum, pre);
        }
        return maxSum;//返回答案
    }
};

复杂度分析

时间复杂度： O(n)。
空间复杂度： O(1)。