信息学竞赛之高效算法—动态规划法

有一组由整数组成的数字，从中抽取连续的一段，求能抽取到的数字之和的最大值。如下列数据：3 -2 1 -1 -4 6 3 -5 5 -9 4 6 -11 8 -7 8 -6 7 -10 2 4 6 -9 3 5 -6 5

这个问题看起来也很简单吧？

如果这组数据全是正数，那么肯定是全选。

如果这组数据全是负数，那么就选绝对值最小的那个。

如果这组数据有正有负，那么选出的这一段肯定不以负数开头，也不以负数结尾。

除此之外，我们还能怎么办呢？如果数据量比较大的话，我们为了保证答案正确似乎也只能不断穷举。穷举的策略就是：依次用不同的数作为开头和结尾，然后累加起来比较，最后得到最大值。这样做的效率是非常低的，如果用这样的策略编制程序，当数据量达到上万以后，连计算机都受不了，需要大约几个小时才能出最终结果。

改进的方法有很多：数组前缀法可以将程序的效率在刚才的基础上提高几千倍，分治法又可以在数组前缀法的基础上提高几百倍，而动态规划法可以在分治法的基础上提高几十倍。采用动态规划法编制的程序连1秒钟都要不到就能出结果。

动态规划法解决问题的策略是：

我们取出的这一段加起来最大的一组数一定以其中的某一个数作为结尾，所以我们可以依次求出以每一个数作为结尾的最大连续段和，然后找出其中的最大者。

以第一个数结尾的最大连续段和就是它自己，那么后续的呢？设以第i个数结尾的最大连续段和为A_i，第i个数为X，那么：

这个式子你看明白了吗？

      有了这个式子，我们就可以从头到尾算一下，直接看出结果。