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

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
 
        //f[i]=array[i]+f[i-1]?
        //no, 一开始就想着必须要用上f[i-1]，其实不一定用得上

        //state transmit program:f[i]=max(f[i-1]+array[i],array[i])
        vector<int> dp(array.size());
        int ret=array[0];
        for(int i=0;i<array.size();i++){
            if(!i){
                dp[0]=array[0];
                continue;
            }
            
            dp[i]=max(dp[i-1]+array[i],array[i]);
            if(dp[i]>ret){
                ret=dp[i];
            }
        }


        return ret;
    }
};