O(n)解决方案

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
      int sum = 0;
      int maxVal = INT_MIN;
      int maxNeg = INT_MIN;
      bool allNeg = true;
      for (int i = 0; i < array.size(); i++) {
        if (array[i] >= 0) allNeg = false;
        if (array[i] > maxNeg) maxNeg = array[i];
        if (sum + array[i] >= 0) {
          sum += array[i];
          if (sum > maxVal) {
            maxVal = sum;
          }
        } else {
          sum = 0;
        }
      }
      return allNeg ? maxNeg : maxVal;
    }
};