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

此题所求为最大的连续子数组的和，而不是具体的子数组，一定程度上降低了题目的难度。使用数组dp[i]来记录的数值，其实并不准确，即其并非最大的子数组的和值。但是对于得到最大的子数组的和值已经足够。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int sz = array.size();
        vector<int> dp(sz+1, 1);
        dp[0] = 0;
        int ret = array[0];
        for (int i = 1; i < sz+1; i++) {
            dp[i] = max(array[i - 1], array[i-1] + dp[i-1]);
            ret = max(ret, dp[i]);  //在此过程中，最大的结果已经得到了
        }
        return ret;
    }
};