问题：有一个数组，求出一个连续的子数组，使这个子数组在所有子数组中各项和最大。
例如：原数组是[1,4,-6,5,2,-1]，则求出的子数组应该是[5,2]，和为7。因为如果是[5,2,-1]，则相加的和是6。
解法有很多，本文只聊动态规划的解法。
事实上，网上能搜到的很多子数组动态规划的解法文章，但是大部分都写的很简略，不适合新手理解。因此本文将循序渐进，一步一步往后讲，内容可能较长，但是很容易理解。
第一步，拆解问题
对于多个可变化的条件，固定多个条件，只留一个变化的条件
题目的要求是：求数组第0项——第n项（n表示数组长度）的最大子集，显然，子集的起始位置和结束位置都不固定的，有两个可变化的条件
我们先固定一端——结束位置，那么问题就变成了
1、当结束位置是0时，求最大子集，这时只需求出起始位置即可
2、当结束位置是1时，求最大子集
.....
n +１、当结束位置是n时，求最大子集
最后，把1,2..., n+1的结果放在一起对比，取出最大的一项即可
第二步，求解其中的一步
我们定义一个函数，getMaxData(end)
函数的作用是：求以end结尾时的最大子集
函数返回值为：一个对象，对象的value属性表示最大值，startIndex表示起始位置，例如{ value:100, startIndex:5 }
显然分两种情况
1、end=0时，只有一项，最大和也是这一项，起始位置也是0。 即{ value:arr[0], startIndex:0}
2、end > 0时，求出[0, end], [1,end],....[end - 1, end], [end] 各个数组的和，取最大的即可。
以上是标准的做法，事实上就是把所有情况都求解，取最大的一个，相信代码都会写。
第一步优化
对于上述第二步，当end > 0时，可以优化为两种情况
1、如果 getMaxData(end - 1)的值大于0，那么getMaxData(end - 1) + arr[end] 显然是最getMaxData(end)的最优解
2、如果 getMaxData(end - 1)的值小于0， getMaxData（end)的解是 arr[end] 自身。因为只要结果带上end - 1，即[x, y, z, ..., end -1, end] 那么x--end -1的和必然小于0，此时再加上end的值，肯定比end自身小。
具体代码如下
当完成getMaxData(end)函数中，计算0-n所有getMaxData的结果，取出最大的一项即可。代码如下
此时，已求解出最终结果，但是仍可进一步优化。往下看
填表
例如，求解 getMaxData(3) 要用到getMaxData(2)，求解getMaxData(4)要用到getMaxData(3)，从而又要用到getMaxData(2)
先从getMaxData(2)求解，把getMaxData(2)保存起来，以后要用到时，直接取出结果即可，修改后的代码如下
红框是新增的内容，第1处的作用是，如果缓存中有end结尾的结果，直接返回，第2处是检查是否存在递归。
从输出结果看，确实没有递归，因为当求第n项时，第n-1项的结果已经先求出来并缓存了。
最后的验证
为了验证性能，我们做一个实验，把数组增大400倍。
当使用缓存时，耗时2毫秒
如果不把结果放到缓存中，耗时为169毫秒。可见填表对性能的优化是很大的，这也是动态规划有别于遍历的重要一环。
