转移方程 $f(i)=max(f(i−1)+nums[i],nums[i])$。可以理解为当前有两种决策，一种是将第 $i$ 个数字和前边的数字拼接起来；另一种是第 $i$个数字单独作为一个新的子序列的开始。

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

另一种动态规划的理解方式：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        //f[i]代表所有以nums[i]为结尾的数列中的最大子序和；last代表f[i -1]的状态
        for (int i = 0, last = 0; i < nums.size(); i++) {
            last = max(last + nums[i], nums[i]);
            res = max(res, last);
        }
        return res;
    }
};