算法-最大子数组之和
最近小编在面试过程中，遇到这个题目，特地总结一下。这是一道考的烂的不能再烂的题目，但是依然有很多公司乐于将这样的题目作为笔试或面试题，足见其经典。
问题描述
原始题目如下：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。扩展题目如下：
炒股的人都知道，股票的价格是不稳定的。若想从炒股中赚钱，必须“低买高卖”，
就是低价买进，高价卖出，赚取中间差价。
那么给定一段时间，每一天都对应着不同的股价，
如何确定哪天买进，哪天卖出可以获得最大收益呢？问题转化
原始问题的意图比较好理解，扩展题目是需要求解一个卖出时间和买入时间的最大价格差。表面上并不是一个字数组之和的题目。我们假设股票价格序列P，
价格差序列为D，其中
Di = Pi - Pi-1
这样的话，P的最大价格差问题就转化为价格差序列D的最大字数组之和的问题。
问题求解
Anyway，就算你没有想到问题形式的转化，也可以通过暴力求解的方式来解决。
尝试每一对可能买入和卖出的时间组合，寻找最大值，暴力破解，双层循环。
其实动态规划最擅长的就是寻找最优解，看样子是很适合这个问题。那我们尝试来寻找最优子表达式。
那需要找到两要素，问题的状态（定义），以及状态转换方程。
问题定义：
在数组A中寻找最大子数组之和
Max[0,i]是第i个元素的最大子数组之和，Max[0,0] = A[0]
状态转换：
那我怎么找到Max[0,i+1]， Max[0,i+1]有两种可能:
一种是最大子数组包含A[i+1]
一种是最大子数组不包含A[i+1]
如果最大子数组包含A[i+1]，那么以A[i]为结尾的最大子数组在加上A[i+1] 是最大子数组
状态转移方程如下
Max[0,i+1] = max {Max[0,i], EndMax[0,i] +A[i+1]}
这里我们需要求解一下EndMax[0,i]，以A[i]结尾的最大子数组
伪代码如下：
其实这个问题还能再简化，降低为线性扫描法。
线性扫描法其实是对EndMax的求解做了优化，但是当最大字段和是小于0，则无法计算正确结果。
考虑EndMax[0,0] = A[0]
EndMax[0,1] = max{A[1], EndMax[0,0] + A[1]}
如果EndMax[0,i]是小于0，那么EndMax[0,i+1]从A[i+1]开始重新计算。（出自编程珠玑）