动态规划处理“线”上的问题非常在行,今天我们就来探讨求解最大字段和的问题。
问题是这样的。

给定N个整数,要求求出最大的连续子段的和。
例如给定:1 -4 3 1 -2
其最大子段和为:4
该子段为:3 1

我们先来分析这个问题。我们最直观的方法就是穷举所有的子段并求和,找到其中最大的,即为答案,但是明显这样做,效率太低。题目中涉及到了“子段”,这使我们想到动态规划的通过寻找“最优子结构”来找到“最优解”的思路。
给定的N个数字存在数组A[N]当中,然后用B[N]来记录子段和的状态。读者可能有疑问,一个串的子串明显不会只有N个,那为什么只用N个元素来记录状态呢?这样做的原因正是因为我们使用动态规划的思路,B中存储的是状态,串中的每个数字的状态只考虑一次。
那么我们来考虑状态转移方程该如何构造:
假设我们已经得到了一个局部最大子串和B[K-1],考虑算上下一个元素A[K]的时候,这个子串的和为B[K] = B[K – 1] + A[K],
这里算出来B[K]如果大于或等于零,则一定有B[K] + A[K + 1] > = A[K + 1];
如果算出来B[K]小于零,则意味着B[K] + A[K + 1] < A[K + 1],也就是这个连续子串和的大小会比单个元素的串还要小,这时候这个子串就已经不可能再成为最大了,所以从这个元素开始“重新打鼓另开张”,开始一个新的连续子串的状态记录。
写成状态转移方程就是:

B[K] = max(B[K – 1] + A[K], A[K])

实现这个动态规划我们仍旧是两个大方向:

1.记忆化搜索
2.递推

对于记忆化搜索,我们可以把状态转移方程改为

B(K) = max(B(K – 1) + A[K], A[K])

用数组B[K]来存储每次地归来的过程,递归函数就是这样的:

这是按照状态转移方程得来的,使用记忆化搜索,要注意处理边界情况,也就是令B[0] = A[0]。
而对于这样的向下递归的方程而言,我们还有一种更佳的方法来求解,那就是递推法。
所谓递推,解释起来非常像递归的反面,这种方法,是从初值,向结果进行运算。
比如等差数列的递归公式为a[n] = a[n – 1] + d, a[1] = 1,用递归方法就是从a[n]这个未知的未知往前检索,直到能确定某个表达式的值之后,才能返回结果。而递推呢,则是根据公式的变换:a[0] + d = a[1], a[1] + d = a[2] … a[n – 1] + d = a[n],也就是由已知的部分逐步递推到最终想要得到的结果上,对于这个问题来说,用递推法更为直观、方便(注意,递推的初始条件为B[0] = A[0]):

关于此类问题的扩展,可以参阅题目POJ 1050 To The Max

说点什么

您将是第一位评论人!

  Subscribe  
提醒