leetcode53. 最大子数组和

分析

用f[i]来表示数组中第i个位置的最大数组和，那么计算f[i]的时候就需要从f[i-1]转移过来，转移方程为f[i]=max(f[i-1]+nums[i],nums[i]),由于只与f[i]和f[i-1]有关，可以用pre来表示i-1,ans来表示i。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans=nums[0];
        int pre=0;
        for(auto x:nums){
            pre=max(pre+x,x);
            ans=max(pre,ans);
        }
        return ans;
    }
};
``