GESP 七级 · GESP 202312 C++ 七级 第 19 题

给定一个数字序列 $A_1,\ A_2,\ A_3,\ \ldots,\ A_n$，要求 $i$ 和 $j$（$1 \leq i \leq j \leq n$），使 $A_i + \ldots + A_j$ 最大，可以使用动态规划方法来求解。（ ）

这题考动态规划适用范围。拿到题先别急着写代码，想清楚：最大子段和能用贪心吗？能分治吗？能不能用动态规划？DP的核心是‘最优子结构’——当前最优解包含子问题的最优解，最大子段和显然满足这一点，所以选A。

很多学生一听到‘动态规划’就条件反射想写复杂的DP，或者误以为DP只能用于计数、路径规划等‘高级’问题，从而否定这种基础应用。其实DP的本质就是利用重叠子问题和最优子结构来避免重复计算，最大子段和恰恰是最典型的DP应用场景之一。命题人故意用‘可以使用’这种绝对化表述，就是想看你是否真正理解DP的适用范围，而不是死记硬背题型。

【考点】动态规划｜最大子段和｜最优子结构

1. 考纲定位：本题考查《GESP 考试大纲》算法模块中动态规划的应用，是六级至七级的核心考点。命题人之所以放这道题，是因为它卡住了绝大多数考生对‘动态规划适用范围’的认知——很多学生误以为动态规划只能用于计数或路径问题，完全没想到它同样适用于求最优值。

2. 解题思维：看到题，先识别这是经典的‘最大子段和问题’。关键观察是：定义 dp[i] 为‘以第 i 个元素结尾的最大子段和’，则状态转移方程为：dp[i] = max(dp[i-1] + A[i], A[i])。这样，通过遍历数组，最后取 dp 最大值即为答案。这一类题的通法是：先定义状态，再找状态转移方程，最后求全局最优解。这个思路可以迁移到最大子树和、最长递增子序列等动态规划问题。

3. 陷阱拆解：命题人利用的思维误区是‘动态规划只用于计数问题’。错误选项 B 的陷阱在于，学生若只背结论而不理解动态规划的本质，就会误判。题目最阴险的细节是‘可以使用’这种绝对化表述——它要求学生判断可行性，而非具体实现。如果你认为‘动态规划太复杂，肯定不能用于简单子段和问题’，那就是掉进了这个坑。

4. 反命题思维：如果把题目改成‘最大子段和可以使用贪心算法求解’，答案就变成错误，因为贪心无法处理动态变化；改成‘可以使用分治法求解’，答案正确但实现更复杂。刷到类似题时，先问自己‘命题人想考我什么’——这里考的是对动态规划适用范围的认知，而非具体代码。

5. 考频趋势：动态规划在题库共考过 120 题，覆盖 9 个考试级别（2009-2026），其中 GESP 七级考过 29 题，说明该考点在七级考试中非常高频。从逐年分布看，2023 年考过 14 题、2024 年 24 题、2025 年 25 题、2026 年 30 题，呈现逐年上升趋势，尤其是 2026 年达到峰值，说明命题人越来越重视动态规划的应用考察。分赛事来看，GESP 六级 38 题、七级 29 题、八级 18 题，说明该考点在 GESP 体系中占据重要地位。

6. 预测：基于上述数据，未来 GESP 七级考试中动态规划相关题目仍将持续高频出现，且可能会更多结合实际问题背景（如最大子段和、最大子树和等）进行考察。暂无足够依据预测具体题型变化，但建议考生重点掌握动态规划的基本思想和常见应用场景，特别是最大子段和这类基础题型的解题思路。