回答思路

线性时间算法：该算法在每次元素累加和小于0时，从下一个元素重新开始累加。实现代码如下： /* 时间复杂度O（n） 和最大的子序列的第一个元素肯定是正数 因为元素有正有负，因此子序列的最大和一定大于0 */ int MaxSubSum(int *arr,int len) { int i; int MaxSum = 0; int CurSum = 0; for(i=0;i<len> MaxSum) MaxSum = CurSum; //如果累加和出现小于0的情况， //则和最大的子序列肯定不可能包含前面的元素， //这时将累加和置0，从下个元素重新开始累加 if(CurSum < 0) CurSum = 0; } return MaxSum; }</len>