O(n)解决方案
连续子数组的最大和
http://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
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;
}
};
