Posted on 2008-04-07 20:16
小夜 閱讀(317)
評論(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