这是我面试的时候想到的算法的实现,使用分治法,算法复杂度为O(n*log(n))。算法描述如下: 对于每一个划分子序列需要获取4个数值: sum(子序列和)、maxSum(最大子序列和)、lMaxSum(最大的含有最左侧节点的子序列和)、rMaxSum(最大的含有最右侧节点的子序列和) 递归算法(res为需要运算的结果,lRes、rRes分别为该段的左右划分): res->sum = lRes->sum + rRes->sum; res->lMaxSum = max(lRes->lMaxSum, lRes->sum + rRes->lMaxSum); res->rMaxSum = max(rRes->rMaxSum, rRes->sum + lRes->rMaxSum); res->maxSum = max3(lRes->maxSum, rRes->maxSum, lRes->rMaxSum + r
![](http://blog.csdn.net/volant_hoo/aggbug/2256611.aspx)
文章来源:
http://blog.csdn.net/volant_hoo/archive/2008/04/07/2256611.aspx