手写代码：最大子数组问题（要求时间复杂度最佳）

参考回答：

线性时间算法：该算法在每次元素累加和小于0时，从下一个元素重新开始累加。实现代码如下：

int MaxSubSum(int *arr,int len){int i;int MaxSum = 0;int CurSum = 0;for(i=0;i<len;i++){CurSum += arr[i];if(CurSum > MaxSum)MaxSum = CurSum;

//如果累加和出现小于0的情况，

//则和最大的子序列肯定不可能包含前面的元素，

//这时将累加和置0，从下个元素重新开始累加

if(CurSum < 0)CurSum = 0;}return MaxSum;}