53. 最大子数组和（dp）

动态规划
令f(i)表示以索引值为i的元素作为区间结尾的最大和
则可以分成两种情况讨论：

1. 区间长度大于等于2
2. 区间长度为1

在第二种情况中，很显然：

f(i) = nums[i]
1

而在第一种情况中，我们可以简单枚举一下可能出现的区间情况，寻找规律：

[i-1, i]

[i-2, …, i]

…

[0, …, i]

可以发现最右边都是nums[i]，而左边是f(i-1)，于是：

f(i) = f(i-1) + nums[i]
1

因此：

f(i) = max{nums[i], f(i-1) + nums[i]}
f(i) = nums[i] + max{0, f(i-1)}
1
2

在代码中我们使用last存储和更新f(i)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN;
        for (int i = 0, last = 0; i < nums.size(); ++i) {
            last = nums[i] + max(last, 0);
            ans = max(ans, last);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11