Markdown那么好，还不来试试扒一扒你遇到过最NB开发项目5月问答又送C币咯！Hadoop实战高手速成宝典
【算法】2 由股票收益问题再看分治算法和递归式
分类：Algorithm
回顾分治算法
分治算法的英文名叫做“divide and conquer”，它的意思是将一块领土分解为若干块小部分，然后一块块的占领征服，让它们彼此异化。这就是英国人的军事策略，但我们今天要看的是算法。
如前所述，分治算法有3步，在上一篇中已有介绍，它们对应的英文名分别是：divide、conquer、combine。
接下来我们通过多个小算法来深化对分治算法的理解。
二分查找算法
问题描述：在已排序的数组A中查找是否存在数字n。
1）分：取得数组A中的中间数，并将其与n比较 2）治：假设数组为递增数组，若n比中间数小，则在数组左半部分继续递归查找执行“分”步骤 3）组合：由于在数组A中找到n后便直接返回了，因此这一步就无足轻重了
平方算法
问题描述：计算x的n次方
我们有原始算法：用x乘以x，再乘以x，再乘以x，一直有n个x相乘
这样一来算法的复杂度就是。
分治算法：我们可以将n一分为二，于是，
当n为奇数时，
当x为偶数时，
此时的复杂度就变成了。
斐波那契数
斐波那契数的定义如下：
当然，可以直接用递归来求解，但是这样一来花费的时间就是指数级的为黄金分割数。
然后我们可以更进一步让其为多项式时间。
上面这幅图虽然比较简略，在求n为6时的斐波那契数，我们却求解了3次F3，F1和F0的求解次数则更多了，我们完全可以让其只求解一次。
对此，还有一个计算公式：
其中是黄金分割率的共轭数。
然后这个公式只存在与理论中，在当今计算机中仍旧无法计算，因为我们只能使用浮点型，而浮点型都有一定的精度，最后计算的时候铁定了会丢失一些精度的。
下面再介绍一种平方递归算法：
一时忘了矩阵怎么计算成绩，感谢@fireworkpark 相助。
最大子数组问题
最近有一个比较火的话题，股票，那么这一篇就由此引入来进一步学习分治算法。在上一篇博客中已经对插入排序和归并排序做了初步的介绍，大家可以看看：【算法基础】由插入排序看如何分析和设计算法
当然了，这篇博客主要用来介绍算法而非讲解股票，所以这里已经有了股票的价格，如下所示。
天 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
股票价格 50 57 65 75 67 60 54 51 48 44 47 43 56 64 71 65 61 73 70
价格波动 0 7 8 18 -8 -7 -6 -3 -3 -4 3 -4 13 10 7 -6 -4 12 -3
价格表已经有了问题是从哪一天买进、哪一天卖出会使得收益最高呢？你可以认为在价格最低的时候买入，在价格最高的时候卖出，这是对的，但不一定任何时候都适用。在这里的价格表中，股票价格最高的时候是第3天、价格最低的时候是第11天，怎么办？让时间反向行驶？
就像我以前参加学校里的程序设计竞赛时一样，也可以用多个for循环不断的进行比较。这里就是将每对可能的买进和卖出日期进行组合，只要卖出日期在买进日期之前就好，这样在18天中就有种日期组合，也可以写成。因此对于种组合，而。
然后，我们在学习算法，自然要以算法的角度来看这个问题。比起股票价格，我们更应该关注价格波动。如果将这个波动定义为数组A，那么问题就转换为寻找A的和最大的非空连续子数组。这种连续子数组就是标题中的最大子数组（maximum subarray）。将原表简化如下：
数组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
A 7 8 18 -8 -7 -6 -3 -3 -4 3 -4 13 10 7 -6 -4 12 -3
在这个算法中，常常被说成是“一个最大子数组”而不是“最大子数组”，因为可能有多个子数组达到最大和。
只有当数组中包含负数时，，最大子数组问题才有意义。如果所有数组元素都是非负的，最大子数组问题没有任何难度，因为整个数组的和肯定是最大的。
使用分治思想解决问题
我们将实际问题转换为算法问题，在这里也就是要寻找子数组和所处的位置必然是以下情况之一：
1）完全位于子数组中，因此； 2）完全位于子数组； 3）跨越中点。
青春一经典当即永不再赎
