Posted on 2008-04-07 20:16
小夜 閱讀(323)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
[05] 算法 、
[51] C&C++
這是我面試的時(shí)候想到的算法的實(shí)現(xiàn)，使用分治法，算法復(fù)雜度為O(n*log(n))。算法描述如下： 對(duì)于每一個(gè)劃分子序列需要獲取4個(gè)數(shù)值： sum（子序列和）、maxSum（最大子序列和）、lMaxSum（最大的含有最左側(cè)節(jié)點(diǎn)的子序列和）、rMaxSum（最大的含有最右側(cè)節(jié)點(diǎn)的子序列和） 遞歸算法（res為需要運(yùn)算的結(jié)果，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