最大子序列和有关问题

最大子序列和问题

问题描述：

给定一个整数序列，a0, a1, a2, …… , an（项可以为负数），求其中最大的子序列和。如果所有整数都是负数，那么最大子序列和为0；

例如：对于序列-2， 11， -4， 13， -5， –2。 所求的最大子序列和为20（从11到13，即从a1到a3）。

用于测试下面代码的的主函数代码如下：（注意要更改调用的函数名）

int maxSubSum3_4( const vector<int> &a ) { int maxSum = 0; int thisSum = 0; for(int j=0; j<a.size(); j++ ) { thisSum += a[j]; if(thisSum>maxSum) { maxSum = thisSum; } else if( thisSum>0 ) { //do nothing } else if( thisSum < 0 ) { thisSum = 0; } } return maxSum; }

分析：

① 只有一层循环，时间复杂度为O(n)。常量空间，线性时间，这是最优解法。