(本文作者：Amαdeus，未经允许不得转载哦。)
给定一个长度为len的序列:a[0],a[1],a[2]...a[len-1]，求在这个序列中一个子区间[j,i]使得a[j]+a[j+1]+...+a[i]的和最大，并求出这个最大累加和。比如一个序列为{-6,7,-1,5,11,-7,2}，那么其最大子段和结果为22，所求子区间范围是[1,4]。
最优子结构:原问题的最优解包含了子问题的最优解。
假设求得了某两个最大子段和区间，分别为[j,i]和[j,i-1]，前一个子区间的元素分别为{a[j],a[j+1]...a[i]}，后一个子区间的元素分别为{a[j],a[j+1]...a[i-1]}。我们很容易发现，后一个子区间[j,i-1]同时也是前一个子区间[j,i]的子区间。
假设我们的两个子区间范围内的最大累加和分别是maxA和maxB，那么可以得出maxA必然包含了maxB。也就是说maxA=maxB+a[i]or0，当a[i]为正数时，我们可以加上a[i]，这样[j,i]的最大累加和相较于[j,i-1]就更大；当a[i]为负数时，我们加上它之后只会减小区间[j,i]的最大累加和，相较于[j,i-1]反而更小，所以此时不加上a[i]。
由此可见，最大子段和问题是满足最优子结构性质的。
对于最大子段和问题，我们都是在先前的状态基础上更新当前的最优解。假设求得之前某个最大子段和区间[j,i-1]，那么我们现在要求区间[j,i]的最大累加和，那么我们只需要在之前区间[j,i-1]确定状态的基础上，更新当前区间[j,i]的最优解，这个问题就是在上一个小标题里我说到的是否加上a[i]。
由此可见，最大子段和是满足无后效性的。
重叠子问题:在过程中重复计算相同的子问题，即子问题之间不是相互独立的，子问题的最优解在之后的决策中会被用到。在上面的阐述中也已经提到，假设我们求得某两个最大子段和子区间分别是[j,i]和[j,i-1]，区间[j,i-1]的最大累加和maxB是先前已经确定的状态，我们求解[j,i]的最大累加和maxA需要用到这个maxB，无需再次计算maxB。
很显然，最大子段和问题也是满足重叠子问题性质的。
综上，我们可以用动态规划算法来求解最大子段和(最大子数组累加和)问题。
1、首先我们需要定义dp[]数组来记录每个状态下的最优解；
2、为了还原最优解，我们需要定义rec[]数组来记录边界下标；
3、构建递推方程，求出最大子段和，并还原具体最优解。
在求解这个问题时，我想到了两种求解最大子段和问题的思路。一种是从前往后记录的方法，一种从后往前记录的方法(这些名字都是我自己取的)。下面我会分别介绍这两种思路，并且给出各自的递推方程。
我们的dp[]数组，在这个从前往后记录的方法中，记录的是以下标为i为结尾下标的子区间的最大累加和，与此同时rec[]数组记录的是对应以下标为i为结尾下标的子区间的左边界(这些很重要)。也就是说，如果我们的最大子段和最终答案是dp[i]，那么对应的区间是[rec[i],i]，我们也可以定义left=rec[i],right=i，这样更清晰一点。初始情况下，dp[0]=a[0],rec[0]=0。
我们以{4,-5,8,9,-19,3,6,-1,10,-2}为例
说实话这个思路略有一点逆思维，其实只是扫描方向的区别，就好像是把数组翻转一下，事实证明从后往前记录的顺序也是同样可以解决最大子段和问题的，只不过我在网上很少看到有人写，所以决定自己来写一下。
不同的是我们的dp[]数组，在这个从后往前记录的方法中，记录的是以下标为i为起始下标的子区间的最大累加和，与此同时rec[]数组记录的是对应以下标为i为起始下标的子区间的右边界(这些还是很重要)。也就是说，如果我们的最大子段和最终答案是dp[i]，那么对应的区间是[i,rec[i]]，我们也可以最后定义left=i,right=rec[i]。初始情况下，若数组最后一个下标为n，那么dp[n]=a[n],rec[n]=n。(注意和之前方法的不同哟~)
在递推过程中，我们发现每一次更新当前区间范围最优解dp[i]，只用到了上一层的dp[i-1](或者dp[i+1])。那么我们是否可以不用dp[]数组呢？答案是可以的。我们可以定义一个变量sum，来一直记录当前子区间范围的最优解。这样可以省去dp[]数组，虽然我自己写代码时使用的动态分配存储空间的数组，后期能够回收内存空间。主要是对于不太会用这个技巧的童鞋，省去dp[]数组，可以节省一定的存储空间。
同时为了还原具体最优解，rec[]也不能闲着，还是需要记录其边界。若为从前往后记录，那么rec[i]在sum>0时就等于rec[i-1]；在sum<=0时就等于i。并且还需要一个right不断记录右边界。若为从后往前记录，那么rec[i]在sum>0时就等于rec[i+1]；在sum<=0时就等于i。并且还需要一个left不断记录左边界。