GESP 五级 · GESP202609 C++ 五级 第 14 题

下面函数使用迭代方法求最大连续子段和。对于数组 {-2, 3, -1, 5, -6, 2} ，函数返回值是 （　　）。

int maxSubArray(const vector<int> &a) {
int best = a[0];
int current = a[0];
for (int i = 1; i < (int)a.size(); i++) {
current = max(a[i], current + a[i]);
best = max(best, current);
}
return best;
}

最大子段和是经典DP模型。看到题先识别出这是Kadane算法的模板实现——用两个变量维护「以当前位置结尾的最大和」与「全局最大和」。核心观察是递推式current = max(a[i], current + a[i])：要么从a[i]重新开始，要么延续前一段。这类题通法是：先确认初始值（通常取第一个元素），再按顺序迭代更新，最后返回全局最优。

选项A=5是数组中最大单元素，混淆了「最大子段和」与「最大元素」；选项B=6可能误把3+5+(-1)+2=9算错成6，或是只加正数3+5-1=7却记错；选项D=8可能是把3+5+2=10误减2得8，或把-6误当+6。最阴险的陷阱是：学生容易忽略current的「重启」逻辑，以为current始终累加，导致算出3+(-1)+5+(-6)+2=3或3+(-1)+5=7却误以为要包含-6。

1. 考纲定位

本题考查《GESP 五级大纲》「算法设计」模块中的动态规划与最大子段和问题。命题人放这道题，就是要卡住那些只会暴力枚举子段、不会用 Kadane 算法的学生——五级要求掌握经典 DP 模型，这道题就是检验你是否真正理解「状态转移」与「最优子结构」。

2. 解题思维

函数用迭代实现 Kadane 算法。看到题先想：这是求最大子段和，标准解法就是维护两个变量——best（全局最优）和 current（以当前位置结尾的最优）。关键观察是递推式 current = max(a[i], current + a[i])：要么从 a[i] 重新开始，要么延续前一段。这类题通法是：先确认初始值（通常取第一个元素），再按顺序迭代更新，最后返回全局最优。