第17课最大子列和问题-2025-2026学年中职三年级c语言程序课程下册

第17课《 最大子数列的求解 》 参赛教师：王凯 中职三年级下册C语言程序设计课程 2026年祁阳市优质教学资源评选活动 1 最大子数列 一 在一队数字数列中，数字有正数和负数，如何在数列中快速找到一段连续的子数列，使得子数列各个元素之和最大。 如有数列 -2, 5, -8, 9, -1, 2, 7, -5, 3 这九个数字中，如何利用算法快速求得连续子数列中的最大和的值是多少？ 二 求出最大子数列的和 枚举算法也称为穷举法，它是算法设计中最常见的方法之一。枚举算法的基本思路是对问题的所有可能状态一一测试，直到找到解或将全部可能状态都测试完为止。枚举法是一种简单、直接地解决问题的方法。枚举算法是基于计算机运算速度快这一特性，在解决问题时采用的一种“懒惰”策略。枚举算法是学习算法的基础，很多算法的优化都是在枚举算法的基础上进行的。 -2 5 -8 9 -1 2 7 -5 3 A 1 2 3 4 5 6 7 8 9 二 枚举算法的解析 枚举算法是解决最大子数列问题的一种简单方法。首先三重循环遍历保存数列的数组A，生成所有可能的子数列并计算它们的和。然后，返回具有最大和的子数列。 二 枚举算法的伪代码 输入有n个数的A[1，2，3，……n] = for i=1 to n for j=i to n sum=0 //sum是当前子数列的和 for k=i to j sum = sum+a[k] //当前的子数列和更新为i到j之间的数字之和 =max(,sum) //K的一次i到j的循环结束后，将和sum与比较，更新 ① ② ③ ① ：第一重循环i，由数列的头到尾② ：第二重循环j， 由i到数列的尾 ③：第三重循环k，由i到j之间的数字组成 二 枚举算法的改进 输入有n个数的数组 A[1，2，3，……n] = for i=1 to n sum=0 //sum是当前子数列的和 for j=i to n sum = sum+a[j] //当前的子数列和更新 =max(,sum) //j每加一次，就将和sum与比较，更新 ① ② ① ：第一重循环i，由数列的头到尾② ：第二重循环j， 由i到数列的尾 j每次加1，都计算子列和的sum值，并且马上与最大值作比较 二 枚举算法的改进C语言代码 二 枚举算法的改进C语言代码 二 求出最大子数列的和 动态规划算法只需遍历一次数列就可以得到最大子数列。 动态规划算法的核心思想是： 遍历数列，在每一个位置 i， 我们决定是“延续”之前的子数组和，还是“重新开始”。 如果 current_max + nums[i] 比自己还小，也就是数组的第i个值 还小，说明之前的累加产生了负贡献，我们果断从数组的第i个值，nums[i] 重新开始计算。 二 动态规划算法 二 动态规划算法的C语言代码 二 动态规划算法的C语言代码 二 动态规划算法的C语言代码 三 课程小结 对比维度 三重循环枚举法 二重循环优化枚举法 动态规划法 循环层数 3层（i、j、k） 2层（i、j） 1层（仅遍历数列一次） 时间复杂度 O(n³)（n为数列长度） O(n²) O(n)（最优） 空间复杂度 O(1)（仅用少量变量存储和与下标） O(1) O(1) 核心优势 逻辑简单、直观，易理解和编写，适合入门理解问题本质 兼顾直观性与效率，消除重复计算，代码修改量小 效率最高，时间复杂度最优，适合实际工程应用 核心不足 大量重复计算，效率极低，数据量大时无法使用 仍存在嵌套循环，数据量极大时效率不足 逻辑需理解动态规划思想，入门难度略高 适用场景 小型数组、算法入门教学、理解子列枚举逻辑 中等规模数组、对效率有一定要求但无需最优解 大型数组、实际项目开发、对效率要求高的场景 三 课程小结 2025 年湘超联赛，永州队以 “永冲锋” 之姿踏浪而来。永州队条件艰苦却斗志弥坚，最终捧起湘超冠军奖杯，用热血与坚韧书写草根逆袭的传奇。这就是足球团队展现了最大子列和的优势，最终收获最大的成果。 五 $