CSP-S 提高级 · CSP 2021 提高级第一轮 第 17 题

(2)

  假设输入的所有数的绝对值都不超过 $1000$ ，完成下面的判断题和单选题：

判断题

22. 程序总是会正常执行并输出两行两个相等的数。（ ）

23. 第 28 行与第 38 行分别有可能执行两次及以上。（ ）

24. 当输入为 5 -10 11 -9 5 -7 时，输出的第二行为 7。( )

单选题

25. solve1(1, n) 的时间复杂度为（ ）。 A. $O(\log n)$ B. $O(n)$ C. $O(n \log n)$ D. $O(n^{2})$

26. solve2(1, n) 的时间复杂度为（ ）。 A. $O(\log n)$ B. $O(n)$ C. $O(n \log n)$ D. $O(n^{2})$

27. 当输入为 10 -3 2 10 0 -8 9 -4 -5 9 4 时，输出的第一行为（ ）。 A. 13 B. 17 C. 24 D. 12

这题考分治求最大子段和。拿到题先别急着套公式，顺着代码看递归怎么切分、怎么合并，特别是跨越中点那一段怎么算，把输入数组和递归过程在脑子里模拟一遍，就能抓住得分点。

很多同学习惯把分治和 Kadane 算法搞混，或者在算跨越中点的和时，只往一边延伸，忘了要左右两边分别找最大后缀和最大前缀再相加。还有同学容易把第一个输入的 n 当成数组第一个元素去处理，导致数组越界或逻辑全错。另外，判断第 28、38 行执行次数时，没注意到递归树中同一行代码在不同层级会被多次调用，只盯着某一次递归，就会误判。

这道题考查的是分治算法在最大子段和问题上的应用，以及递归函数的执行流程和时间复杂度分析。命题人喜欢挖的坑主要在三点：一是递归边界和参数传递（n 是长度还是下标），二是跨越中点的计算逻辑，三是时间复杂度的推导。拿到题，先别急着背结论，要顺着代码看：函数把区间一分为二，分别求左半、右半的最大值，再求跨越中点的最大值，最后取三者最大。这个“切分—求解—合并”的过程就是分治的核心。

概念与命题视角：最大子段和就是找一个连续子数组，使其和最大。分治法把大问题拆成小问题，递归解决。命题人特意给了两个版本 solve1 和 solve2，其实是在考你对递归树的理解：solve1 是标准分治，solve2 可能用了不同的合并策略或递归写法。判断题 22 考的是两个版本结果一致性；判断题 23 考的是递归中某行代码被调用的次数（容易误以为只在顶层执行一次）；判断题 24 考的是具体数值计算，这里最容易错的就是跨越中点的和算错。

思考心法与具体计算： 1. 审题：第一个输入的数是数组长度 n，后面才是 n 个元素。很多同学习惯把 n 当成第一个元素，结果数组越界或逻辑全错。本题给定输入是 5 -10 11 -9 5 -7，实际数组是 [-10, 11, -9, 5, -7]，n=5。 2. 模拟递归：solve1(1,5) 会把区间分成 [1,2] 和 [3,5]，递归下去。跨越中点的和需要从中间向两边扩展：左边找最大后缀（从中间往左加），右边找最大前缀（从中间往右加），两者相加。对于 [-10, 11, -9, 5, -7]，最大子段和就是单个元素 11，不是 7，所以判断题 24 选错误。 3. 执行次数：第 28 行和第 38 行在递归的不同层级会被多次调用。例如 solve1(1,5) 会调用 solve1(1,2) 和 solve1(3,5)，再往下递归，每一层都会执行这两行。因此判断题 23 选错误（它们不会分别执行两次及以上，而是各自在递归树中多次执行，但题目问的是“分别有可能执行两次及以上”，结合代码逻辑，这两行在互斥分支中，不会同时都执行两次及以上）。 4. 时间复杂度：solve1 是标准分治，递推式 T(n) = 2T(n/2) + O(n)，由主定理得 O(n log n)，单选题 25 选B。solve2 虽然写法不同，但本质上仍然是分治，合并步骤也是 O(n)，所以复杂度同样是 O(n log n)，单选题 26 选C（这里命题人可能故意让 solve2 看起来像线性扫描，但仔细看递归结构，它依然是分治，所以选 C）。 5. 最后一题：输入 10 -3 2 10 0 -8 9 -4 -5 9 4，数组为 [-3, 2, 10, 0, -8, 9, -4, -5, 9, 4]。最大子段和是 2+10+0+(-8)+9+(-4)+(-5)+9+4 = 17，单选题 27 选B。

避坑指南：

• 别把 n 当成数组第一个元素处理。
• 跨越中点的和一定要左右两边都找最大后缀和最大前缀再相加，只往一边延伸是典型错误。
• 判断题 23 容易误以为某行只在顶层执行一次，其实递归树中每层都会执行，但题目问的是“分别有可能执行两次及以上”，结合代码逻辑，这两行在互斥分支中，不会同时都执行两次及以上，所以选错误。

考频与趋势：分治算法在题库共考过 79 题，覆盖 8 个考试级别（2007-2026），其中 2024 年考了 17 题，2025 年考了 14 题，2026 年考了 15 题，可见分治是近年高频考点，尤其在 CSP 提高级和 GESP 六级、五级中占比很大。递归函数共考过 115 题，2024 年更是考了 25 题，2025 年 15 题，2026 年 18 题，说明递归思想是考试重点。结合这两组数据，未来分治与递归结合的题目（如本题）大概率会持续出现，且难度可能向动态规划与分治融合的方向发展。

预测：基于 2024-2026 年分治和递归的高频趋势，未来考试很可能继续考分治求最大子段和，或者将其与动态规划结合，增加考察深度。暂无足够依据预测具体题目形式，但建议重点复习分治的递归树分析和时间复杂度推导。