算法导论--最大子数组问题
最大子数组问题：
问题描述：
假定你获得了投资挥发性化学公司的机会。与其生产的化学制品一样，这家公司的股票价格也是不稳定的。你被准许可以在某个时刻买进一股该公司的股票，并在之后某个日期将其卖出，买进卖出都是在当天交易结束后进行。为了补偿这一限制，你可以了解股票将来的价格。你的目标是最大化收益。
虽然最高价卖出，最近价买进是收益最大化，但是在一段给定时期内，可能无法做到在最低价格时买进股票，然后在最高价格时卖出。
- 最简单的暴力求解方式就是计算任意两天之间的价格差，然后找到差最大的那个。
然后就能使得收益最大化。
但是这种方式的运行时间为。 这个运行时间为什么是
这里涉及的数学知识是排列组合：
An 2 /2 = 17*16/2=136 种组合方式 n(n-1)/2
如果用程序语言排序需要两个循环也就是的复杂度。
我们换一种方法：价格差也就是变化差距，我们找到连续的时间段内的价格
差距相加最大的那个数组，然后在数组头买进，数组尾卖出，这样就能最大
化收益了暴力**转换成寻找最大子数组问题。
从上面两个图可以看到，当连续的数组相加的值最大的是时候就是最大盈利时候。
这种把问题换成求最大子数组的问题其实本质上还是排列组合问题
只不过是从每天价格的问题改成了找两天价格差的组合：
每天的价格：
价格变化：
我们仍然需要检查 C n-1 2 =θ(n²)个子数组 C n-1 2 表示 (n-1)(n-2)/2
那么我们把问题转换为寻找最大子数组问题之后，怎么解决这个时间复杂度和渐进增长问题呢？？
我们需要寻找最大子数组问题的更高效的解决方法，不然 问题转化就毫无意义：
我们通常说一个最大子数组 而不是最大子数组，因为可能有多个子数组达到最大和。只有当数组中包含负数时，最大子数组问题才有意义，如果所有数组元素都是非负的，最大子数组问题没有任何难度，因为整个数组的和肯定是最大的。
我们使用分治策略解决问题：
假定我们要寻找子数组A[low,high]的最大子数组，使用分治技术意味着我们要将子数组划分为两个子规模尽量相等的子数组，也就是说，找到了子数组的中央位置mid。然后考虑求解两个子数组A[low,mid] 和A[mid+1,high]:
最大子数组必然是这三种情况之下。
我们就是要在数组中找出这三种情况的最大子数组然后比较。
第一个和第二个就比较好说了，直接用暴力求解就行了。
第三个跨越子数组，这个其实可以理解为左边半边到mid点的最大子数组+ 右边mid点到右边某个点之内的最大子数组的和。因为跨越子数组 必然是要连接mid点的。所以只需要左边连接mid最大+右边连接mid最大，但是注意左边连接mid最大并不等于左边最大，这个跨越中的限制必然是要连接中点。
所以只要左边连接mid最大+右边连接mid最大就是跨越中点最大了
伪代码：
求左边最大子数组和右边最大子数组用分治法，求中间最大值则另外求解，