最大子數組問題

分治策略中，我們遞歸的求解一個問題，在每層遞歸中應用如下三個步驟：

分解：將問題劃分為一些子問題，子問題的形式和原問題一樣 ，只是規模更小。

解決：遞歸的求解子問題。

合併：將子問題的解組合成原問題的解。

最大子數組問題：

一個數組，元素為正整數和負整數，尋找其中和最大的連續序列。

A[low..high]的任何連續子數組A[i..j]所處的位置必然是以下三種情況之一：

• 完全位於子數組A[low..mid]中，low i j mid 。
• 完全位於子數組A[mid+1..high]中，mid < i j high 。
• 跨越了中點，low i mid < j high 。

Find-Max-SubArray(A,low,high)if high == low return (low,high,A[low])else mid = (low+high)/2 (left-low,left-high,left-sum) = Find-Max-SubArray(A,low,mid) (right-low,right-high,right-sum) = Find-Max-SubArray(A,mid+1,high) (cross-low,cross-high,cross-sum) = Find-Max-Cross-SubArray(A,low,mid,high) (max-low,max-high,max-sum)= Max(left-sum,right-sum,cross-sum) return (max-low,max-high,max-sum)Find-Max-Cross-SubArray(A,low,mid,high)left-sum = -MAXsum = 0for i = mid downto low sum = sum + A[i] if sum > left-sum left-sum = sum max-left = iright-sum = -MAXsum = 0for j = mid + 1 to high sum = sum + A[j] if sum > right-sum right-sum = sum max-right = jreturn (max-left,max-right,left-sum + right-sum)

推薦閱讀：