分治算法是一种思想，所以比一般算法更难使用。
1.划分问题（Divide）：将原问题分成一系列子问题。
2.递归解决（Conquer）：递归地解各子问题。若子问题足够小，则可直接求解。
3.合并问题（Combine）：将子问题的结果合并成原问题的解。
![[算法]NOI竞赛：简单分治及其应用（一）](http://p2.ttnews.xyz/loading.gif)
·给出一个长度为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
·由于这样的子序列的和可以表示为（Ai+Ai+1+…+Amid）+（Amid+1+…+Ar）的形式，只需找到一个l使得Ai+.…+Amid最大，再找到一个r使得Amid+1+…+Ar最大，加起来即得到结果。
·将得到的结果与F(L.mid),F(mid+1.R)取最大值，即得到F(L，R)。（合并问题）
时间复杂度为O(nlogn)
-给出一个长度为n的序列A，输出将它从小到大排序之后的结果。
-n≤10^5 （排序问题）
归并排序
·假设现在要将区间[L，R]内元素的排序，借鉴之前的思想，我们可以令mid=（L+R）/2，先递归地将[L.mid]和[mid+1.R]内的元素分别排好序。
现在需要将两边的序列合并在一起，可以维护两个指针p.q.一开始令p=L，q=mid+1.并建立一个序列B表示新的序列。若A[p]
分享到:
閱讀更多 學點乾貨 的文章
