分治算法是一種思想，所以比一般算法更難使用。

1.劃分問題（Divide）：將原問題分成一系列子問題。

2.遞歸解決（Conquer）：遞歸地解各子問題。若子問題足夠小，則可直接求解。

3.合併問題（Combine）：將子問題的結果合併成原問題的解。

·給出一個長度為n的序列A.求一個和最大的連續子序列。也就是要找出一對l.r（1≤l≤r≤n）.使得Ai+A(i+1)+…+A(r-1)+A，最大。

·n≤10^5（最大子序列問題)

·暴力枚舉：

枚舉l，r，對於每對l，r計算這段子序列的和，對所有結果取最大值即為答案。

暴力計算時間複雜度為O(n^3)。

一個優化是記錄前綴和，即記錄S[i]=A1+A2+…+Ai.那麼子序列[l.r]的和即為S[r]-S[l-1]。

前綴和優化後複雜度為0(n2)。

分治解法

·設F（L.R）表示L到R這段區間內的和最大的子序列，答案就是F(1.n)。

考慮分治，假設現在要計算F（L，R）.設mid=（l+R）/2.可以先遞歸計算F（L，mid）

以及F（mid+1.R）。（劃分問題，遞歸解決）

·注意到對於一個子序列[L.rl.L≤l≤r≤R.若l≤mid

閱讀更多 學點乾貨 的文章

關鍵字: 算法 枚舉 Tor