算法设计和研究课程中最大子段与问题教学探析摘要介绍算法设计与分析课程中最大子段和问题的动态规划解法，其求解思想是先求给定序列中以每一个元素为尾元素的最大子段和，然后其中的最大者便是整个序列的最大子段和。从两个不同的角度分析最大子段和问题最优解的构造方法，给出最大子段和问题的动态规划算法，并分析算法的时间复杂度。通过这一问题的讲解，有助于学生明确动态规划方法的解题步骤,掌握动态规划算法的设计步骤。关键词最大子段和；动态规划；时间复杂度：G642.4文献标识码：B:1671-489X(2013)27-0050-03最大子段和问题出自于2005年浙江大学计算机专业研究生入学考试计算机专业基础综合试题，它是一个典型的最优化问题该问题描述为：给定由n个整数(可能为负整数)组成的序列al,a2,...,an,其中，ai,ai+1,・.・,aj-1,aj(lWiWjWn)称为序列al，a2,...,an的一个子段，显然子段中的元素是连续的，该子段中所有整数的和称为该子段的和。对于序列al,a2,...,an来说，它有很多不同的子段，每个子段都有一个和，要求出该序列的各个子段的和的最大值，当序列中所有整数均为负整数时定义其最大子段和为o[l-2]。该问题的解法有多种，笔者在算法设计与分析课程的授课过程中，针对该问题给出了三种求解方法，分别是枚举法、分治法和动态规划方法。用枚举法求最大子段和问题，时间复杂度为0(n2)；用分治法求最大子段和问题，其算法的时间复杂度可以降到0(nlog2n)；而如果用动态规划方法求解最大子段和问题，其时间复杂度仅为0(n),效率要比枚举法和分治法高很多。这里主要探讨该问题的动态规划解法，包括求解该问题的最优值和构造该问题的最优解，最优值是指给定序列的最大子段和是多少，最优解是指和最大的子段是哪一个子段。1求解最大子段和问题的一种新思路设a[l：n]是一个含有n个元素的整型数组，用a[l]〜a[n]这n个单元来存储n个整数，a[0]空闲不用。对于数组a来说，它有许多不同的子段，每个子段都有唯一的一个首元素，也有唯一的一个尾元素。那么对于数组a来说，它的所有子段的尾元素的下标位置的范围是从1到n的，即子段的尾元素的下标位置可以是1,这时这个子段就是由a[l]本身构成的，子段的尾元素的下标位置也可以是2,依此类推，子段的尾元素的最后一个下标位置是n。因此可将数组a的所有子段分成n种，第一种是以数组元素a[l]为尾元素的子段，第二种是以数组元素a[2]为尾元素的子段，依此类推，第n种是以数组元素a[n]为尾元素的子段。显然每种子段都有一个最大子段和，那么数组a的最大子段和就是这n个最大子段和中的最大者。因此可先求以数组元素a[l]为尾元素的最大子段和，再求以数组元素a[2]为尾元素的最大子段和，依此类推，一直求到以数组元素a[n]为尾元素的最大子段和，则整个数组的最大子段和就是这n个最大子段和中的最大者。若用数组元素b[j]来表示以数组元素a[j]为尾元素的最大子段和，则整个数组的最大子段和就是，于是求整个数组的最大子段和就转化为求各个b[j]o下面来讨论如何用动态规划方法求b[j]o2用动态规划方法求b[j]动态规划方法求解问题的第一步就是分析最优解的性质，并刻画它的结构特征，也就是证明这个问题具有最优子结构性质，即证明问题的最优解中是否包含了子问题的最优解。2.1最优子结构性质假设子段｛a[s],a[s+l],…，aEj-1],a[j]｝是以a[j]为尾元素的最大子段，也就是说b[j]=o那么必有子段｛a[s],a[s+l],…，a[j-l]｝—定是以a[j-l]为尾元素的最大子段，也就是说必有b[j-l]=o假设子段｛a[s],a[s+l],…，a[j-l]｝不是以a[jT]为尾元素的最大子段，以a[j-l]为尾元素的最大子段是｛a[r],a[r+1],…，a[j-l]｝,r或大于s或小于s,则必有。只要在子段｛a[r],a[r+l],…，a[jT]｝的后面加上一个元素a[j],就能得到另外一个以a[j]为尾元素的子段｛a[r],a[r+l],…，a[j-l],a[j]｝,这个子段的和可表示为+a[j],显然有+a[j]>+a[j]=b[j]。这里假设a[j]不为0,这显然与b[j]是以a[j]为尾元素的最大子段和相矛盾，也就是与假设的｛a[s],a[s+l],…，a[j]｝是以a[j]为尾元素的最大子段相矛盾。因此，如果｛a[s],a[s+l],…，a[j-1],a[j]｝是以a[j]为尾元素的最大子段，那么就必有...