文章编号：1671-489X（2013）27-0050-03
最大子段和问题出自于2005年浙江大学计算机专业研究生入学考试计算机专业基础综合试题，它是一个典型的最优化问题。该问题描述为：给定由n个整数（可能为负整数）组成的序列a1，a2，...，an，其中，ai，ai+1，...，aj-1，aj（1≤i≤j≤n）称为序列a1，a2，...，an的一个子段，显然子段中的元素是连续的，该子段中所有整数的和称为该子段的和。对于序列a1，a2，...，an来说，它有很多不同的子段，每个子段都有一个和，要求出该序列的各个子段的和的最大值，当序列中所有整数均为负整数时定义其最大子段和为0[1-2]。
该问题的解法有多种，笔者在算法设计与分析课程的授课过程中，针对该问题给出了三种求解方法，分别是枚举法、分治法和动态规划方法。用枚举法求最大子段和问题，时间复杂度为O（n2）；用分治法求最大子段和问题，其算法的时间复杂度可以降到O（nlog2n）；而如果用动态规划方法求解最大子段和问题，其时间复杂度仅为O（n），效率要比枚举法和分治法高很多。这里主要探讨该问题的动态规划解法，包括求解该问题的最优值和构造该问题的最优解，最优值是指给定序列的最大子段和是多少，最优解是指和最大的子段是哪一个子段。
1 求解最大子段和问题的一种新思路
设a[1：n]是一个含有n个元素的整型数组，用a[1]～
a[n]这n个单元来存储n个整数，a[0]空闲不用。
对于数组a来说，它有许多不同的子段，每个子段都有唯一的一个首元素，也有唯一的一个尾元素。那么对于数组a来说，它的所有子段的尾元素的下标位置的范围是从1到n的，即子段的尾元素的下标位置可以是1，这时这个子段就是由a[1]本身构成的，子段的尾元素的下标位置也可以是2，依此类推，子段的尾元素的最后一个下标位置是n。因此可将数组a的所有子段分成n种，第一种是以数组元素a[1]为尾元素的子段，第二种是以数组元素a[2]为尾元素的子段，依此类推，第n种是以数组元素a[n]为尾元素的子段。显然每种子段都有一个最大子段和，那么数组a的最大子段和就是这n个最大子段和中的最大者。
因此可先求以数组元素a[1]为尾元素的最大子段和，再求以数组元素a[2]为尾元素的最大子段和，依此类推，一直求到以数组元素a[n]为尾元素的最大子段和，则整个数组的最大子段和就是这n个最大子段和中的最大者。若用数组元素b[j]来表示以数组元素a[j]为尾元素的最大子段和，则整个数组的最大子段和就是，于是求整个数组的最大子段和就转化为求各个b[j]。下面来讨论如何用动态规划方法求b[j]。
2 用动态规划方法求b[j]
动态规划方法求解问题的第一步就是分析最优解的性质，并刻画它的结构特征，也就是证明这个问题具有最优子结构性质，即证明问题的最优解中是否包含了子问题的最优解。
2.1 最优子结构性质
假设子段{a[s]，a[s+1]，…，a[j-1]，a[j]}是以a[j]为尾元素的最大子段，也就是说b[j]=。那么必有子段{a[s]，
a[s+1]，…，a[j-1]}一定是以a[j-1]为尾元素的最大子段，也就是说必有b[j-1]=。
假设子段{a[s]，a[s+1]，…，a[j-1]}不是以a[j-1]为尾元素的最大子段，以a[j-1]为尾元素的最大子段是{a[r]，a[r+
1]，…，a[j-1]}，r或大于s或小于s，则必有。只
要在子段{a[r]，a[r+1]，…，a[j-1]}的后面加上一个元素a[j]，
就能得到另外一个以a[j]为尾元素的子段{a[r]，a[r+1]，…，
a[j-1]，a[j]}，这个子段的和可表示为+a[j]，显然有+a[j]>+a[j]==b[j]。这里假设a[j]不为0，这显然与b[j]是以a[j]为尾元素的最大子段和相矛盾，也就是与假设的{a[s]，a[s+1]，…，a[j-1]，a[j]}是以a[j]为尾元素的最大子段相矛盾。因此，如果{a[s]，a[s+1]，…，a[j-
1]，a[j]}是以a[j]为尾元素的最大子段，那么就必有{a[s]，
a[s+1]，…，a[j-1]}一定是以a[j-1]为尾元素的最大子段，即问题的最优解中包含了子问题的最优解，最优子结构性质成立。
2.2 建立b[j]的递推关系
对于本问题来说，建立最优值的递推关系就是建立b[j]与b[j-1]之间的关系。在证明最优子结构性质时，其实已经给出了b[j]与b[j-1]之间的关系，b[j]其实就比b[j-1]多了一个a[j]，但这里还需要根据b[j-1]的数值特性将此关系式细化，因为子段的和b[j-1]可以为正，可以为负，也可以为零[3]：
如果b[j-1]>0，则b[j]=b[j-1]+a[j]；
如果b[j-1]<=0，则b[j]=a[j]。
在这两种情况中，无论a[j]为何值，都是成立的，因为b[j]是以数组元素a[j]为尾元素的最大子段和，a[j]是必须包含的。
2.3 以自底向上的方式计算各个b[j]
所谓自底向上方式是指由最小子问题的解构造较小子问题的解，由较小子问题的解构造较大子问题的解，由较大子问题的解构造最大问题的解。对于这个问题来说，最小的子问题就是b[1]，而由b[j]满足的递推关系式可知，求b[1]时需要判断b[0]的数值特性，由于b[1]表示的是以a[1]为尾元素的最大子段和，而以a[1]为尾元素的子段就只有一个，就是由a[1]自身所构成的子段。所以b[1]=a[1]，而在递推关系式中b[j]=a[j]的条件是b[j-1]<=0，所以在求解b[1]之前，可令b[0]=0。求出b[1]后，根据b[1]的数据特性求b[2]；求出b[2]后，根据b[2]的数据特性求b[3]，依此类推，直到求出b[n]为止，最后b[1]，b[2]，…，b[n]中的最大者就是整个数组a的最大子段和。
下面通过一个例子来详细说明动态规划方法求解给定数组的最大子段和的过程。给定一个含有5个元素的数组a，这5个整数分别为-2，11，-4，13，-5，则数组b的值如表1所示。显然b[4]最大，为20，因此数组a的最大子段和为20。
下面根据上述思想写出用动态规划方法求解最大子段和问题的算法。
3 最大子段和问题的动态规划算法
最大子段和问题的最优值的求解思想就是先求b[1]，b[2]，
…，b[n]，然后这n个值中的最大者就是整个数组a的最大子段和。
最大子段和问题的最优解就是和最大的子段到底是哪个子段。要确定和最大的子段，只需要知道和最大的子段的首尾元素的下标即可。在最优值的求解算法中，要先求b[1]，b[2]，…，b[n
]，然后这n个值中的最大者就是整个数组a的最大子段和。假设b[1]，b[2]，…，b[n]中的最大者是b[f]，即整个数组的最大子段和sum的值就是b[f]，而b[f]的含义是以a[f]为尾元素的最大子段和。因此，整个数组的最大子段和就是以a[f]为尾元素的最大子段和，即和最大的子段的尾元素已经确定，就是a[f]。知道了尾元素是a[f]，又知道了最大子段和是sum，那么只需要去考察以a[f]为尾元素的每一个子段，然后计算当前考察的子段的和，如果这个和等于sum，就找到了和最大的子段，记录当前子段的的首元素即可；反之如果这个和不等于sum，就继续考察以a[f]为尾元素的下一个子段。
要考察以a[f]为尾元素的每一个子段，就是要枚举以a[f]为尾元素的每一个子段的首元素的下标位置。以a[f]为尾元素的子段有很多，包括a[1]，a[2]，a[3]，a[4]，a[5]，…，
a[f]、a[2]，a[3]，a[4]，a[5]，…，a[f]、a[3]，a[4]，a[5]，…，
a[f]、a[4]，a[5]，…，a[f]，最后一个就是a[f]这个元素本身。可以按照从f到1的顺序去枚举首元素的下标，这样可以充分利用上一次计算的结果。因为按照从f到1的顺序去枚举首元素的下标，以a[f]为尾元素的第一个子段就是a[f]；以a[f]为尾元素的第二个子段就是a[f-1]，a[f]，显然这个子段只比上一个子段多了一个当前子段的首元素而以；以a[f]为尾元素的第三个子段就是a[f-2]，a[f-1]，a[f]，显然这个子段也只比上一个子段多了一个当前子段的首元素。这样，当前子段的和就等于上一个子段的和再加上当前子段的首元素。如果当前子段的和等于sum，就找到了和最大的子段，只需记录当前子段的首元素即可，反之就继续考察以a[f]为尾元素的下一个子段，直至找到和最大的子段的首元素为止。找到了首尾元素的下标，就构造出了问题的最优解。
求解最优值和构造最优解的算法如算法1所示。在算法1中，构造最优解的过程还可以进一步优化，方法是在递推求解b[i]的过程中直接记录首元素的下标，因为当b[i-1]<=0时，b[i]=a[i]，即这时更新了当前子段的首元素，当前子段的首元素就是a[i]；而当b[i-1]>0时，b[i]=b[i-1]+a[i]，这时只是进一步扩大了当前子段的范围。因此，只需当b[i-1]<=0时，记录当前子段的首元素的下标即可，即令s=i，当算法结束时，s就是和最大子段的首元素下标。优化后的算法如算法2所示。该算法的时间复杂度为O（n）。
4 结论
文章分析了算法设计与分析课程中最大子段和问题的动态规划解法，其求解思路是先求以数组元素a[1]为尾元素的最大子段和，再求以数组元素a[2]为尾元素的最大子段和，依此类推，一直求到以数组元素a[n]为尾元素的最大子段和，则整个数组的最大子段和就是这n个最大子段和中的最大者。然后分析了该问题最优解的构造方法，最后给出了该问题的动态规划算法，并分析了算法的时间复杂度。通过这一问题的讲解，有助于学生明确动态规划方法的解题步骤，掌握动态规划算法的设计步骤。
参考文献
[1]王晓东.算法设计与分析习题解答[M].北京：清华大学出版社，2006.
[2]王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2007.
[3]袁佳乐.浅析求解最大子段和问题的算法[J].西安文理学院学报：自然科学版，2009（3）：96-99.
