最大子數組問題——分治策略

這篇博客是學習《演算法導論》的筆記（P.S.代碼使用Python）。

用分治法解決問題，大致的步驟如下：

• 分解(Divide)：將問題劃分為一些子問題，子問題形式與原問題一樣，但是規模變小了。
• 解決(Conquer)：遞歸地將求解子問題，當子問題規模足夠小的時候停止遞歸，直接求解。
• 合併(Combine)：將子問題的解組合成原問題的解。

如果你通過某種手段獲得了未來若干天里的某家公司的股票價格走勢，你可以在某一時刻買入股票並在另一個時刻拋出。當然，你希望可以從中獲得最大的利益，比如，對於如下的走勢：

並不是所有的情況下都可以在最低價買入、最高價拋出的，比如如上走勢圖中，最高價發生在第4天但是最低價發生在第8天。

暴力求解：如果簡單地嘗試每個可能的買入和拋出的組合，只需要買入發生在拋出之前即可滿足條件，但是這種方法的效率實在太低，尤其是在天數足夠長的情況下。

使用分治法求解：我們的目的是尋找一段時間，使得獲得的利益最大，如果我們從每日價格的變化入手，第i天的價格變化表示為與前一天的價格差，如果將價格的變化看成一個數組arr，如此，問題就變成了尋找arr的和最大的非空連續子數組，也即是最大字數組。

假定我們尋找數組arr[low..high]的最大子數組，使用分治法的意思是我們需要將它劃分為盡量規模一樣的兩個子數組。就是說，找到數組的中間位置mid，然後分別求解arr[low..mid]和arr[mid+1..high]，arr[low, high]的最大子數組arr[i..j]必然屬於如下三種情況之一：

• 完全位於子數組arr[low..mid]中，因此low<=i<=j<=mid。
• 完全位於子數組arr[mid+1..high]中，因此mid<i<=j<=high。
• 跨越了中點mid，此時low<=i<=mid<j<=high。
  於是我們使用函數find_max_crossing_subarray()來求解跨越中點的情況下的解，它返回跨越中點的最大子數組的左右邊界以及最大子數組的值，然後分別與arr[low..mid]和arr[mid+1..high]的解比較，得出最後的答案。

def find_max_crossing_subarray(arr, low, mid, high):n left_sum = -9999999999n sum = 0n # 求出左邊的最大子數組arr[max_left_pos, mid]n for left_pos in xrange(mid, low-1, -1):n sum += arr[left_pos]n if sum > left_sum:n left_sum = sumn max_left_pos = left_posnn right_sum = -9999999999n sum = 0n # 求出右邊的最大子數組arr[mid+1, max_right_pos]n for right_pos in xrange(mid+1, high+1):n sum += arr[right_pos]n if sum > right_sum:n right_sum = sumn max_right_pos = right_posnn return max_left_pos, max_right_pos, left_sum + right_sumn

有了這個求解跨越中點的最大子數組的函數，我們就可以設計求解最大子數組的問題的分治演算法了，find_max_subarray()接收數組arr以及其左右下標為輸入，返回arr[low..high]的最大子數字的左右下標以及值：

def find_max_subarray(arr, low, high):n if high == low:n return low, high, arr[low]nn mid = int((low + high) >> 1)n left_low, left_high, left_sum = find_max_subarray(arr, low, mid)n right_low, right_high, right_sum = find_max_subarray(arr, mid+1, high)n cross_low, cross_high, cross_sum = find_max_crossing_subarray(arr, low, mid, high)n n if left_sum >= right_sum and left_sum >= cross_sum:n return left_low, left_high, left_sumn elif right_sum >= left_sum and right_sum >= cross_sum:n return right_low, right_high, right_sumn else:n return cross_low, cross_high, cross_sumn

在函數find_max_subarray()中，第2行中如果low與high相等，則表示只有一個元素待求解，於是直接返回那一個元素和下標。反之，6~8行分別表示求解arr[low..mid]和arr[mid+1..high]的最大子數組和跨越中點的最大子數組。10~15行比較孰是真正的最大子數組。

通過find_max_subarray()求得，在第8天（第7天結束後）買入，第11天拋出可以得到最大利益。

-------------

P.S.最大子數組問題的最優解：

def find_max_subarray(arr):n now_sum = max_sum = 0n for item in arr:n now_sum += itemn max_sum, now_sum = (max_sum, now_sum)[max_sum < now_sum], (now_sum, 0)[now_sum < 0]n return max_sumn

這個解法叫『在線處理』，意思是隨時停止它，都可以得到目前為止的正確解。 它只需O(n)的時間複雜度，就可以完成求解~~~

推薦閱讀：