Posted on 2008-04-07 20:16
小夜 阅读(310)
评论(0) 编辑 收藏 引用 所属分类:
[05] 算法 、
[51] C&C++
这是我面试的时候想到的算法的实现，使用分治法，算法复杂度为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/archive/2008/04/07/2256611.aspx