最大字段和算法【算法设计与分析课程中最大子段和问题和策略分析】

算法设计与分析课程中最大子段和问题和策略分析

该问题的解法有多种，笔者在算法设计与分析课程的授 课过程中，针对该问题给出了三种求解方法，分别是枚举法、 分治法和动态规划方法。用枚举法求最大子段和问题，时间 复杂度为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.