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

这是个标准的动态规划，需要注意的是明确好dp的意义，因为是要连续数组，所以我们可以规定dp[i]一定包含i

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size()==1) return array[0];
        int ans=array[0];
        vector<int> dp(array.size(),array[0]);//dp是以i结尾的，一定包含当前的最后一个，这样我们只需要再比较一圈那个dp最大即可
        for(int i=1;i<array.size();i++){
            dp[i]=max(dp[i-1]+array[i],array[i]);
            ans=max(dp[i],ans);
        }
        return ans;
    }
};

也可以用贪心。参见热评第一