剑指offer 42-连续k个子数组的最大和

核心方案： 动态规划， 一维， dp[i]表示以第i个元素结尾的子数组的最大和

思路： dp[i] 和 dp[i-1]的关系在于如何用array[i]， 是（之前的最大连续子串保留+第i个元素），还是（只要第i个元素）？

困惑： 这个方案必然是从左遍历到右的，会不会有些贪心的嫌疑？先遇到的好子串，后面新遇到的数只考虑在之前子串上的用处。只有之前子串和<0了才从新开始，是否在不<0的时候就有重新开始的好方案呢？

//通过代码：
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size()<=0)
            return -1;
        else if(array.size()==1)
            return array[0];
        vector<int> maxSeq(array.size());
        maxSeq[0]=array[0];
        
        for(int i=1;i<int(array.size());i++){
            if(maxSeq[i-1]<=0)
                maxSeq[i]=array[i];
            else 
                maxSeq[i]=maxSeq[i-1]+array[i];
        }
        auto indx=max_element(maxSeq.begin(),maxSeq.end());
        return *indx;
    }
};