最大子数组和

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

53.最大子数组和

小黎一开始想用前缀和来做的，就是当前前缀和减去目前最小前缀和，和当前ans取max。但是这样的话对于包含第0个元素的答案是不行的，后面感觉这不就是动态规划的思想嘛，于是转头写动态规划了。

状态转移方程很直观，就是要么取之前数组和当前元素组合成一个数组，要么这个数组新开一个。设$f(i)$为数组前$i$个元素的最大前缀和，状态转移方程为：
$$
f(i) = max(f(i - 1) + nums[i], nums[i])
$$
由于状态转移方程只和前一个结果有关，所以用一个变量存储之前的结果就行。取遍历过程中的最大值作为结果就好。

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