分治策略

如何递归地求解一个问题? 分为三步: 分解、解决、合并。分解的时候只管将问题划分为子问题，即形式与原问题一样，规模更小的问题。解决是待分解到足够小以至于直接求解没有任何困难时，直接求解。合并是将子问题的解组成原问题的解，是一步简单的组合。未完全分解的较大的子问题叫递归情况，不需要再递归的足够小的子问题叫基本情况。

1.递归式描述把问题划分为子问题时，原问题与子问题关系的表达式，如果每一步都把问题分成1:2的大小，且分解与合并的时间为线性，那么可以得到 $T(n)=T(2n/3)+T(n/3)+\Theta(n)$ 的表达式。这种表达式不一定是按比例分解，还可能是按加减法来分解子问题，如求解斐波那契数列的递归方法。

2.递归式的一种常见形式对于 $T(n)=aT(n/b)+f(n)$ ， $a\ge1,b>1$ ，这代表着我们每次分解生成 $a$ 个规模为原来的 $1/b$ 大小的子问题， $f(n)$ 代表分解和合并的时间代价。一般情况下，我们忽略取整问题以及边界条件，例如对奇数归并排序的情况下，不能完全等分为一半大小的子问题，但是不影响我们的求解结果。

3.最大子数组问题假定你知道股票17天内每天的价格，你能找到使得利益最大化的买入和卖出分别是哪一天吗？

天	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
价格	100	113	110	85	105	102	86	63	81	101	94	106	101	79	94	90	97
变化		13	-3	-25	20	-3	-16	-23	18	20	-7	12	-5	-22	15	-4	7

暴力求解 遍历每一种买和卖的可能，这将带给我们 $\Omega(n^2)$ 的代价(根据排列组合)

问题变换 我们的目标是要设计出一个 $o(n^2)$ 的算法，即严格比 $n^2$ 低阶的算法。那么我们需要转换一下思路: 我们聚焦于表格第三行，即股票每天的变化，我们需要找到第三行的一段子数组(连续的一段子集)，使得子数组的元素和最大。乍一看，我们仍然需要检查所有可能的子数组，和暴力求解没什么区别。但我们可以进一步思考一下，想办法利用之前算过的子数组以大幅降低计算量。

采取分治策略 如果我们将数组等分，那么最大子数组可能出现在以下三种情况中的一种: 完全落在左边、完全落在右边以及跨过中点。对于前两种情况直接就是一个更小规模的相同的问题，我们先只管分解不管解决，但第三种情况是一个需要我们去着重处理的新问题: 找到横跨中点的那个最大子数组。然后在每层递归我们都给出这三种情况找到的最大子数组的和，然后通过比较返回最大的那个给上一层递归。对于第三种情况下，我们可以在线性时间内找到跨越中点的最大子数组:

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)//mid是中点，low和high是两边
	left-sum = -INF	//left-sum是一个变量名，下同，INF是一个很大的数
	sum = 0
	for i = mid downto low
		sum = sum + A[i]	//从中间向左边延伸，设法找到向左延伸的最远处
		if sum > left-sum	//如果新加进来的若干元素以后，和变大了，则允许向左延伸
			left-sum = sum
			max-left = i	//更新向左的距离
		right-sum = -INF	//对右侧也做一样的事
		sum = 0
		for j = mid + 1 to high
		sum = sum + A[j]
		if sum > right-sum
			right-sum = sum
			max-right = j
	return (max-left, max-right, left-sum + right-sum)	//返回向左向右延伸的距离以及数组的元素和

解决了这个最棘手的情况，我们的递归程序就呼之欲出了。

FIND-MAXIMUM-SUBARRAY(A, low, high)
	if high == low
		return (low, high, A[low])	//基本情况，递归出口
	else mid = (low + high) / 2
		(left-low, left-high, left-sum) =
			FIND-MAXIMUM-SUBARRAY(A, low, mid)	//找到左半数组的最大子数组
		(right-low, right-high, right-sum) = 
			FIND-MAXIMUM-SUBARRAY(A, mid + 1, high)	//找到右半数组的最大子数组
		(cross-low, cross-high, cross-sum) = 
			FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)	//找到横跨中点的最大子数组
		if left-sum >= right-sum and left-sum >= cross-sum	//返回他们三个最大的那个子数组
			return (left-low, left-high, left, sum)
		elseif right-sum >= left-sum and right-sum >= cross-sum
			return (right-low, right-high, right-sum)
		else return (cross-low, cross-high, cross-sum)

处理横跨中点的情况需要线性时间，基本情况需要常数时间，我们可以得到递归式

T(n)=\begin{cases} \Theta(1),\ n=1 \\ 2T(n/2)+\Theta(n),\ n>1 \\ \end{cases}

可以解出 $T(n)=\Theta(n\lg n)$ ，具体解法将在下面介绍。

用主方法求解递归式 令 $a \ge 1$ 和 $b>1$ 是常数， $f(n)$ 是一个函数， $T(n)$ 是定义在非负整数上的递归式: $T(n)=aT(n/b)+f(n)$ ，则

1.若对某个常数 $\epsilon >0$ ，有 $f(n)=O(n^{\log_ba-\epsilon})$ ，则 $T(n)=\Theta(n^{\log_ba})$

2.若 $f(n)=\Theta(n^{\log_ba})$ ，则 $T(n)=\Theta(n^{\log_ba}\lg n)$

3.若对某个常数 $\epsilon>0$ ，有 $f(n)=\Omega(n^{\log_ba+\epsilon})$ ，且对某个常数 $c<1$ 和所有足够大的 $n$ 有 $af(n/b)\le cf(n)$ ，则 $T(n)=\Theta(f(n))$

其实这三种情况下，我们比较的都是递归的代价和本层的其他的非递归代价哪个占了主导地位，如果 $f(n)$ 的代价很大，那最终结果由 $f(n)$ 决定，如第三个情况。如果 $f(n)$ 更小，如第一种情况，则可以将 $f(n)$ 忽略，得到第一个情况。而剩下的那个情况就如同前文的求解最大子数组的算法，是一个 $n\lg n$ 阶的算法。

举个例子，对于 $T(n)=9T(n/3)+n$ ，比较 $n$ 和 $n^{\log_39}$ ，易知 $\epsilon$ 取1时，符合第一种情况，因此解出 $T(n)=\Theta(n^{\log_39})=\Theta(n^2)$ 。而如果 $T(n)=T(2n/3)+1$ ，我们比较 $1$ 和 $n^{\log_{3/2}1}=1$ ，因此落入第二种情况，解得 $T(n)=\Theta(\lg n)$ 。而如果 $T(n)=3T(n/4)+n\lg n$ ，比较 $n\lg n$ 和 $n^{\log_43}\approx n^{0.8}$ ，我们容易找到 $\epsilon\approx0.2$ ，满足 $f(n)=\Omega(n^{\log_34+\epsilon})$ ，而且 $3f(n/4)=3(n/4)\lg(n/4)\le3(n/4)\lg n=\frac{3}{4}f(n)$ ，因此完全符合第三类情况，因此 $T(n)=\Theta(n\lg n)$ 。