解递归式的方法总结、最大子数组问题（股票买卖）

写在前面：递归是我最头痛的…我最喜欢的老师跟我讲，递归是种玄学。懂的人特别懂，不懂的人怎么都不懂。仿佛你的爱情哈哈哈哈。但我很懂爱情喔。此文参考《算法导论》。

求解递归式

递归式与分治算法密切相关。使用递归式可以很自然地刻画分治算法的运行时间。

求解递归式时间复杂度的方法：

① 代入法

我们猜测一个界，然后用数学归纳法证明这个界是正确的。（渐进界）

• 先对一个小值假设，然后推测更大的值正确性。
• 数学归纳法。猜测。

② 递归树法

将递归式转换为一棵树，其节点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。

举个栗子：

$T(n)=3T(~└~ n/4 ~┘~)+Θ(n^2)$T(n)=3T( └ n/4 ┘ )+Θ(n2)

• 抛去上下界函数影响
• 把Θ($n$n²)用$cn^2$cn2代替

在递归树中，有几个要点，影响最终的结果：

• 每个结点（子代价）
• 每层代价
• 层数

递归树的边界，是到达n为1，也就是$T(1)$T(1)时候。递归次数=递归树深度。在这个例子中，$n$n每次都除以4，除呀除，除到1时，递归就结束了。除了多少呢？
$4^i=n$4i=n
$㏒4n=i$㏒4n=i
其中，i就是递归树的深度。

③ 主方法

$T(n)=aT(n/b)+f(n)$T(n)=aT(n/b)+f(n)

a>=1,b>1,$f(n)$f(n)是一个给定的函数。这种形式的递归式很常见，刻画了这样一个分治算法：
生成a个子问题，每个子问题的规模是原问题规模的1/b，分解和合并步骤总共花费时间为$f(n)$f(n)。

使用主方法，要熟记三种情况。一旦掌握了主方法，确定简单递归式的渐近界就变得很容易。

三种情况如下：

我们偶尔会遇到不是等式而是不等式的递归式。

• $T(n)≦2T(n/2)+Θ(n)$T(n)≦2T(n/2)+Θ(n) 用O描述其解
• $T(n)≧2T(n/2)+Θ(n)$T(n)≧2T(n/2)+Θ(n) 用Ω描述其解

递归式技术细节

在实际应用中，我们会忽略递归式声明和求解的一些技术细节。例如，如果子问题规模为$n/2$n/2，当$n$n为奇数， $n/2$n/2不式整数。但是我们一般忽略这个细节。

另一类，边界条件也是我们通常忽略的细节。对于一个常量规模的输入，算法的运行时间为常量。对于足够小的$n$n，$T(n)$T(n)为常量。因此，下式

$T(n)=2T(n/2)+Θ(n)$T(n)=2T(n/2)+Θ(n)

常作为最终的递归式。省略了n=1的情况。因为n很小时，虽然会改变递归式的精确解，但改变幅度不会超过一个常数因子，函数的增长阶也不会发生变化。

因此求解递归式时，向下取整、向上取整、边界条件等常常忽略。通常影响不大。

最大数组问题

出自《算法导论》。

给出一支股票近15天的价格表，要求求出买进、卖出所能收益的最大值，及买进卖出的时刻。

天数	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

显而易见，有一种思考起来最简单解法：暴力求解。遍历所有的可能情况，选出最大的。这种运行时间为$Ω(n^2)$Ω(n2)

那么，有没有更高效的解法呢？

可以考虑分治法。
把变化当成一个数组，问题转换成求出数组连续的和的最大值。如果数组中不存在负数，就失去了求解的意义。

如何用分治技术解决这个问题呢？分治法求解过程可以分为以下三个阶段

• 划分 Divide
• 求解子问题 Conquer
• 合并 Combine

首先来说划分。怎么划分？最容易想到的就是“一分为二”。把一个数组从中间分开，那么最大子数组存在的情况有三种：左边、右边、横跨左右两个数组。

其次，求解子问题。划分到不能再划分时，相当于递归到了尽头。比较三种情况的的计算结果。

合并。这个没什么解释的，就是合并。

代码之后再写