题解 | #连续子数组的最大和#
连续子数组的最大和
https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
本质上是动态规划，设以下标为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;
}
};
