分治算法是一种思想，所以比一般算法更难使用。
1.划分问题（Divide）：将原问题分成一系列子问题。
2.递归解决（Conquer）：递归地解各子问题。若子问题足够小，则可直接求解。
3.合并问题（ComBine）：将子问题的结果合并成原问题的解。
·暴力枚举：
枚举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<r.那么在递归的子问题中不会考虑到这个子序列。也就是还需要找到最大的经过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]<A[q].则将A[p]加入B的末尾，并令p=p 1.否则将A[q]加入B的末尾，并令q=q 1.
·不断重复这样的操作，直到p>mid或q>R.将剩余还未加入B的元素以此加入B即可。
最后，将日序列复制回来。
·T（n）=2T（n/2） O（n）=O（nlogn）
Merge_sort(L,R): //伪代码 Mid=(L R)/2 Menge_sort(L,Mid),Merge _sort(Mid 1,R) p=L,q=Mid,pos=L While p <=Mid and q<=R do if A[p]<A[q] then B[pos ]=A[p ] else B[pos ]=A[q ] While p<=Mid do B[pos ]=A[p ] While q<=R do B[pos ]=A[q ] For i=L to R do A[i]=B[i]
快速排序
·在之前的分治中，我们总是将当前要解决的区间从中间等分成两半，两边分别解决，快速排序则运用了一种不同的分治方法。
-假设现在仍然要将区间[L.R]排序，我们在[u.R]内随机取一个值x，将所有小于A[x]的元素放在前面，否则放在后面。例如当前要将7，4，2，1，3，3排序，假设随机到x=5.A[x]=3.则数组变为2.1.3.3.7.4。
·假设有cnt个元素小于A[x].则递归地将[L，L cnt-1]以及[L cnt.R]排序。由于前面的元素一定小于后面的元素，递归完成之后数组即为有序。
在期望意义下，我们可以认为每次都会将区间分成长度相差不大的两段，因此快速排序的期望复杂度是O（nlogn）的。
Quick_sort（L，R）//伪代码 x=rand（L，R） p=L,q=R For i=L to R do if A[i]<A[x] then B[p ]-A[i] else B[q-]=A[i] For i=L to R doA[i]=B[i] Quick_sort（L，p-1），Quick_sort（q 1，R） -给出一个长度为n的序列A，输出将它从小到大排序之后的第k个元素的值。·1≤k≤n≤10^7
数据量有些难以接受。快速排序变形
Kth_element（L,R,k） if L==R then return A[L] x=rand(L,R) p=L,q=R For i=L to R do if A[i]<A[x] then B[p ]=A[i] else B[q--]=A[i] For i=L to R.do A[i]=B[i] if k<(p-L) then return Kth_element(L,p-1,k） else return Kth_element(q 1,R,k-(p-L)) ·给出一个序列长度为n的序列A，求A的逆序对个数。·若对于1<i<j<n，Ai>Aj.则称（i,j）是一对逆序对。n≤10^5，A≤10^9 (逆序对计数)
(数据结构)·枚举，我们需要统计有多少.满足i<j且Ai>Aj。
·将A离散化（即令Ai等于Ai在A序列中的从小到大的排名），从小到大地枚举j。令Bi表示有多少个x，满足Ax=i，且x<j。那么我们每次需要查询一段区间Bi的和，并将一个Bi加1。
·可以使用线段树或者树状数组维护，复杂度为O（nlogn）。
(归并排序)·事实上，我们只需要使用类似归并排序的分治就能解决这个问题。
·对于一段区间[L，R].我们需要将区间排好序，并返回这个区间内的逆序对个数。先令mid =(l r)/2，然后向两边递归，就计算出了所有满足L≤i<j≤mid，mid<i<j≤R的逆序对。现在只需要加上满足L≤i≤mid，mid<j≤R的逆序对。
·在将两边的序列合并的过程中，我们可以统计对于每个右边区间的数.在这个数加B序列时，有多少个左边区间内的数还未加入，也就是有多少左边区间的数比它大。将这个值加入答案即可。
·复杂度仍为O(nlogn)
有一个2^k×2^k的方格棋盘，恰有一个方格是黑色的，其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖，且任意一个白色方格不能同时被两个或更多牌覆盖。如下图所示为L型牌的4种旋转方式。·k≤10 (棋盘覆盖问题)·题目是要求用L型牌覆盖一个2k×2k的方格棋盘，棋盘有且只有一个黑色方格，此方格不能覆盖。
·考虑分治，将棋盘平均分为4块，每一块刚好是2^(k-1)x2^(k-1)的方格棋盘，但当前只有一块中含有一个黑色方格，所以要为另外三个方格构造出一个黑色方格，如下图所示：
未完待续，请关注我：学点干货。
