最大m子段和问题(动态规划(又来填表了....))

1.定义

给定由n个整数（可能为负）组成的序列a1、a2、a3...,an, 以及一个正整数m，要求确定序列的m个不相交子段，使这m个子段的总和最大！

如给定一个数组{1，-2，3，4，-5，-6}和一个正整数m=2，明显当两个子段分别为{1}和{3，4}时，得到最大m子段和，最大m子段和为8。

2.思路

可以利用动态规划的思想解决该问题。

定义二维数组dp，令dpi表示前 j 项所构成 i 子段的最大和，且必须包含着第j项，即以第j项结尾。(这个定义很重要，一定要理解)。

举个例子，如dp3则表示以a4结尾，并且和a4前面的项所构成的3子段和的最大值。简单来说，就是a0a1a2a3a4中分成3段，包含a4且以a4结尾，这3子段和是最大的。（例如可能是a0、a1、a4这三段）

所以，dpi总共有两种可能。

1.若aj和aj-1合成一段，此时 dpi = dpi-1 + aj

2.aj单独成段，然后往aj前面的项找i-1个子段最大和，此时dpi = dpi-1+aj

最后取这两种情况中的最大值，赋给dpi。

3.例子

根据思路，实战一把，例如有一个数组

arr={1，-2，3，4，-5，-6}，可以根据以上思路做出下表。例如我们要求图中的星星部分的值，也就是

dp2的值，首先第一种情况是a4与前面的a3连成一段，即该种情况下的dp2的值为dp2+a4=8+(-5) = 3；第二种情况是，a4自成一段，并且看看其之前的项中，i-1段最大和为多少，可以看到为7，所以该种情况下的dp2的值为dp1+a4 = 7 + (-5) = -2；取第一种情况与第二种情况中的最大值，为3，填入dp2中。

我们可以从上往下，从左往右把整张表填完。

那么，假如要求m=2时的最大子段和为多少时，可以看到第2行中，dp2的时候最大，为8。

另外找i-1子段的最大和，可以使用滚动辅助数组来完成，不用重新遍历。即，再上一轮填空的过程中，记录j列之前（包括j列）的最大值，以供此轮填表使用。

4.参考代码

完