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

Answer 1

参考回答：

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

/*

时间复杂度O（n）

和最大的子序列的第一个元素肯定是正数

因为元素有正有负，因此子序列的最大和一定大于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;
}