问题：有一个数组，求出一个连续的子数组，使这个子数组在所有子数组中各项和最大。

例如：原数组是[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毫秒。可见填表对性能的优化是很大的，这也是动态规划有别于遍历的重要一环。