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

套用了动态规划求连续子数组的最大和(一)的写法：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
      // write code here
      int len = array.size();
      
      if (len == 1) {
        return array;
      }
      
      // 两个定义vector，用于记录
      vector<int> v, retv;
      int max = INT_MIN, count = 0;
      for(int i=0; i<len; i++) {
        if (count < 0){
          count = 0;
          v.clear();
        }
        count += array[i];
        v.push_back(array[i]);
        if (count >= max) {
          max = count;
          retv = v;
        }
      }
      
      return retv;
    }
};

最终：时间复杂度：O(n)，空间复杂度：O(n)