最大子數組查找問題

03-06

以股票買賣為背景，假設給定若干天的股票價格，需要找出在哪天買入和哪天賣出可最大化收益。即就是要尋找 $i,j,i>j$ 使得 $p_i -p_j$ 最大。

我們可以很容易的設計出一個暴力方法來求解，簡單地嘗試每對可能的邁進和賣出的日期組合，只要賣出日期在買入日期之後即可， $n$ 天中共有 $C_{n}^{2}$ 種組合， $C_{n}^{2}=Theta(n^2)$ ，吹了每對日期花費的時間是常量，因此運行時間為 $Omega(n^2)$ .

問題轉變

我們定義每日價格差為第 $i$ 天價格與第 $i-1$ 天價格差，這樣我們希望找到 $i,j,i>j$ 使得第 $i$ 天到第 $j$ 天價格差之和最大，也就是尋找A的和最大的非空連續子鼠族，我們稱之為最大子數組(maximum subarray).

這樣看起來好像沒有什麼影響，因為子數組個數為 $C_{n-1}^{2}=Theta(n^2)$ 需要進行檢查，雖然計算一個子數組之和是線性的，但我們可以採用累加的方式來使得每個子數組的求和計算時間為 $O(1)$ ,從而暴力求解的計算時間為 $Theta(n^2)$ 。

採用分治策略

假設需要尋找數組 $A[low,high]$ 的最大子數組，我們將其切分為兩個子數組， $A[low,mid]A[mid+1,high]$ ,採用遞歸的方法進行求解， $A[low,high]$ 的任意連續子數組必然處於以下三種情況之一：

完全位於左子數組 $A[low,mid]$
完全位於右子數組 $A[low,mid]$
跨越了中點

因此我們可以轉化思路，採用遞歸方法進行求解：

求解左子數組 $A[low,mid]$ 的最大子數組
求解右子數組 $A[mid+1,high]$ 的最大子數組
求解 $A[low,high]$ 跨越中點的最大子數組

然後進行比較來得到最大子數組。

1. 求取跨越中點的最大子數組

def find_maximum_subarray_cross_mid(A,low,high,mid): 發現跨越中點的最大 # 計算左邊 left_sum = -100000 all_sum = 0 i = mid left_index = mid while i >= low: all_sum = all_sum + A[i] if all_sum > left_sum: left_sum = all_sum left_index = i i = i-1 # 計算右邊 right_sum = -100000 all_sum = 0 i = mid + 1 right_index = mid while i <= high: all_sum = all_sum + A[i] if all_sum > right_sum: right_sum = all_sum right_index = i i = i+1 return left_index,right_index,right_sum+left_sum

2. 遞歸求取最大子數組

def find_maximum_subarray(A,low,high): 遞歸求取最大子數組 if low == high: return low, high, A[low] mid = (low+high)/2 cross_left,cross_right,cross_sum = find_maximum_subarray_cross_mid(A, low, high, mid) low_left,low_right,low_sum = find_maximum_subarray(A, low, mid) high_left, high_right, high_sum = find_maximum_subarray(A, mid+1, high) if cross_sum > low_sum and cross_sum > high_sum: return cross_left,cross_right,cross_sum elif low_sum > cross_sum and low_sum > high_sum: return low_left,low_right,low_sum else: return high_left, high_right, high_sum

例如

A = [1,2,-3,4,5,-6,7] print find_maximum_subarray(A,0,6)

得到結果最大子數組為 $[4,5,-6,7]$