算法1

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

class Solution {
public:

    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int f[n] = {0};

        f[0] = 0;
        for(int i = 1;i <=n;i++) // f[i] 表示第几个数为结尾的最大的值，我们把nums 相当于从i=1是其实是nums中的第0个
            f[i] = max( nums[i-1],f[i-1]+nums[i-1]);


        int res = -1e8;
        for(int i = 1;i<=n;i++)
            res = max(res,f[i]);
        return res;
    }
};