problem:53. 最大子数组和

思路：
1.前缀和转换为 121. 买卖股票的最佳时机

2.动态规划定义f[i]为以i结尾的最大子数组和，转移方程：f[i] = max(f[i-1],0)+nums[i];答案即为max(f)这个做法也叫做 Kadane 算法

Accode:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //动态规划,dp[i]表示以i结尾的最大子数组的和
        int ans = -0x3f3f3f3f;
        vector<int> dp(nums.size()+1,0);
        for(int i=0;i<nums.size();i++){
            dp[i+1] = max(dp[i],0)+nums[i];
            ans = max(ans,dp[i+1]);
        }
        return ans;
    }
};

时间复杂度：$o(n)$