算法1

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

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        int f[n] = {0};

        // 状态转移方程：f[i] = max(f[i-1] ,0) + nums[i];
        f[0]=nums[0];

        for(int i = 1; i < nums.size() ; i++ ) {
            f[i] = max(f[i-1] ,0) + nums[i];
        }

        int res = -1e8;
        for(int i = 0; i < nums.size() ; i++ ) {
            res = max(res,f[i]);
        }


        return res;
    }
};