#include#include using namespace std;//线性算法int maxSubSum1(const vector & a){ int maxSum, thisSum, i = 0; if (a[0] < 0) { maxSum = a[0]; i++; while (i < a.size()) { if (a[i] < 0) { maxSum = (maxSum > a[i] ? maxSum : a[i]); i++; } else break; } } if (i < a.size()) { maxSum = a[i]; thisSum = a[i]; i++; while (i < a.size()) { if (a[i] > 0) { if (thisSum > 0) { thisSum += a[i]; maxSum = (maxSum > thisSum ? maxSum : thisSum); i++; } else { thisSum = a[i]; maxSum = (maxSum > thisSum ? maxSum : thisSum); i++; } } else { if (thisSum > 0) { if (thisSum + a[i] < 0) { thisSum = a[i]; i++; } else { thisSum += a[i]; i++; } } else { thisSum += a[i]; i++; } } } return maxSum; } else { return maxSum; } }//穷举算法 时间复杂度为N的平方int maxSubSum2(const vector & a){ int maxSum = a[0], thisSum; for (int i = 0; i < a.size(); i++) { thisSum = 0; for (int j = i; j < a.size(); j++) { thisSum += a[j]; maxSum = (maxSum > thisSum ? maxSum : thisSum); } } return maxSum; }//验证函数int main(){ vector a = { 4, -3, 5, -2, -1, 2, 6, -2};//放入任意int数据 cout << maxSubSum1(a) << endl << maxSubSum2(a) << endl; cin.get(); return 0;}
运行结果为
