题解 | #连续子数组的最大和#

本质上是动态规划，设以下标为i结尾的子数组最大和为dp[i]，转移方程为dp[i] = max(0, dp[i - 1]) + array[i]。（如果之前的子数组对和的贡献度为负，那么不如舍弃之前的子数组直接选择当前元素）然后再使用一个res变量记录dp[i]的最大值。

由于dp[i]只与dp[i-1]有关，所以可以优化成一个变量。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int res = array[0], sum = 0;
        for (auto &i: array) {
            sum = max(sum + i, i);
            res = max(res, sum);
        }
        return res;
    }
};