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

参考自链接
  我们分析一下这道题，全局最优解是序列子数组的最大和，但是这里我们可以把这道题进行一个拆分：
  1.求以arr[i]结尾的子数组最大和组成的数组dp
  2.数组dp中求最大值
  这样我们就可以得到一个dp方程：dp[n] = Max(dp[n - 1] + arr[n], arr[n]);（这道题的难点就在于这里，需要进行一个转换

class Solution {
public:

    int FindGreatestSumOfSubArray(vector<int> arr) {
        int length = arr.size();
        int max = arr.at(0);
        vector<int> dp (length, 0);
        dp.at(0) = arr.at(0);
        for(int i = 1; i < length; ++i)
        {
            dp.at(i) = std::max(dp.at(i - 1) + arr.at(i), arr.at(i));
            max = std::max(dp.at(i), max);
        }
        return max;
    }
};