剑指 Offer 42. 连续子数组的最大和

剑指 Offer 42. 连续子数组的最大和

思路：

f[i] 表示以a[i] 结尾的子串的最大和，f[i] 划分以a[i]选或不选，如果选即f[i - 1] + a[i] > a[i] ，如果不选则相反。

代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int prsum = 0;
        int res = INT_MIN;
        for(int i = 0; i < n; i++){
            prsum = max(nums[i],prsum + nums[i]);
            res = max(res,prsum);
        }
        return res;
    }
};