53. 最大子序和/C++

暴力求解，从前往后遍历，如果所得和小于0，则舍弃前面的所有元素；如果所得和大于max，则记录下来。

int maxSubArray(vector<int>& nums) {
    if(nums.empty())
        return 0;
    
    int sum = 0, max = INT_MIN;
    for (auto i : nums) {
        sum += i;
        if (sum > max) max = sum;
        if (sum < 0)   sum = 0;
    }
    return max;
}

动态规划
f(n)是以第n个数结尾的最大和
f(n)=max(f(n-1)+nums[i],nums[i])

int maxSubArray(vector<int>& nums) {
    if(nums.empty())
        return 0;
        
    int res = INT_MIN;
    int f = -1;
    for(auto i : nums){
        f = max(i, f + i);
        res = max(f, res);
    }
    return res;
}