PAT 甲级题目讲解：1007《Maximum Subsequence Sum》

✅ PAT 甲级题目讲解1007《Maximum Subsequence Sum》摘要本文是 PAT 甲级 1007 题《Maximum Subsequence Sum》的完整题解围绕最大连续子序列和这一经典问题从题目约束分析入手结合样例直观演示字典序优先规则的判断过程。核心解法采用 Kadane 算法以线性时间动态维护当前子序列和与全局最优解并详细拆解了前缀和为负则重启的关键决策逻辑。文中提供了变量说明表、分步代码实现以及完整可运行 C 代码最后梳理了常见错误类型与复杂度分析帮助读者透彻理解并安全落地该算法。 题目简介本题是经典的最大连续子序列和Maximum Subsequence Sum问题。若存在多个最大和相同的子序列请输出最先出现的那个也就是起点索引i最小的子序列如果起点相同则终点索引j更小的子序列优先即“最小字典序优先”。给定一个长度为KKK的整数序列{N1,N2,...,NK}\{N_1, N_2, ..., N_K\}{N1​,N2​,...,NK​}要求找出和最大的连续子序列并输出该子序列的最大和子序列的第一个元素值子序列的最后一个元素值。特殊约定若所有数均为负则最大子序列和为0同时输出整个序列的首尾元素。 样例分析输入样例10 -10 1 2 3 4 -5 -23 3 7 -21观察整个序列-10 1 2 3 4 -5 -23 3 7 -21手动分析所有可能的子序列存在两个最大和相同的子序列1 2 3 4和3 7其和均为10根据题目要求选择字典序最小的那个即起点较小的1 2 3 4起点在下标 1终点下标 43 7起点下标 7虽更短但下标更大不选。因此最终输出10 1 4 解题思路本题核心是动态规划的思想即使用前缀局部最优信息逐步更新整体最优。 Kadane 算法核心思想Kadane 算法解决的问题是如何在线性时间内找出连续子序列的最大和它的核心思想是对于当前遍历到的元素aia_iai​我们维护一个当前连续子序列的和s如果s 0说明前面的累计对后续结果有害应从当前位置i重新开始新的子序列否则继续将当前元素加入子序列每次迭代后都尝试更新全局最大子序列和maxs。✅ 数学表达假设当前遍历到位置iii我们有若前缀和s0s 0s0则s:ai s : a_is:ai​否则继续累加s:sai s : s a_is:sai​然后更新最大值maxs:max⁡(maxs,s) \text{maxs} : \max(\text{maxs}, s)maxs:max(maxs,s) 为什么要重启因为如果当前的累计和是负数继续加上后续数字只会让总和更小所以遇到负和时果断重启子序列更优。 基本策略用一个变量s记录当前连续子序列的和如果当前和s小于0则重置从当前位置重新开始每次更新时判断是否比历史最大和更优。 变量说明变量名含义k输入整数序列长度a[]原始整数序列s当前子序列的累加和tp当前子序列起点索引p最终答案中子序列起点索引q最终答案中子序列终点索引maxs当前为止的最大子序列和f标记是否存在非负数用于特殊判断✅ Step 1输入与特判处理scanf(%d,k);for(inti0;ik;i){scanf(%d,a[i]);if(a[i]0)f1;// 存在非负数}if(!f){// 所有数为负直接输出规则要求的形式printf(0 %d %d,a[0],a[k-1]);return0;}✅ Step 2Kadane 算法主过程采用经典的最大子序列求和算法每次遍历更新最大和并记录位置maxsINT_MIN;// 初始化为最小整数for(inti0;ik;i){if(s0){// 当前子序列的累加和为负值tpi;// 当前位置作为新的起点sa[i];// 重置当前和}else{sa[i];// 累加当前值}if(smaxs){maxss;// 更新最大和ptp;// 更新起点qi;// 更新终点}}✅ Step 3输出结果最终输出的是最大和 起点值 终点值printf(%d %d %d,maxs,a[p],a[q]);✅ 完整代码#includebits/stdc.husingnamespacestd;intk,a[10005],s,tp,p,q,maxs;boolf;intmain(){scanf(%d,k);for(inti0;ik;i){scanf(%d,a[i]);if(a[i]0)f1;}if(!f){printf(0 %d %d,a[0],a[k-1]);return0;}maxsINT_MIN;for(inti0;ik;i){if(s0){tpi;// 更新序列起点sa[i];}else{sa[i];}if(smaxs){maxss;ptp;qi;}}printf(%d %d %d,maxs,a[p],a[q]);return0;} 常见错误提醒错误类型错误表现所有元素为负时处理错误忘记特判导致输出错误或数组越界maxs初始值不当考虑到只有负数和 0 的情况不能初始化为 0 -1 或者INT_MIN正确子序列起点更新不当忘记在s 0时更新tp导致区间定位错误最大和判断顺序错应在每次s maxs时更新序列起始位置与和起点与终点输出的是索引应输出对应值a[p],a[q]而非下标✅ 总结归纳本题核心是经典的 Kadane 算法在遍历时使用s 0作为重启标志特判所有为负数的情况同时跟踪子序列的起点和终点方便输出原始数值。⏱️ 复杂度分析时间复杂度O(n)\mathcal{O}(n)O(n)空间复杂度O(n)\mathcal{O}(n)O(n)由于存储输入序列 思维拓展若要求输出所有等价最大子序列如何存储多个答案若改为“最大乘积子序列”应如何调整本题也可以作为滑动窗口 动态规划的变种训练。