26 届携程笔试：最大子数组区间取优、非递减数组最小代价与 AI Coding

《面试题目》

1. AI Coding 题：在既有代码基础上继续优化评分（作者反复调整后仍在 8324 与 8342 之间）。
2. 编程题：最大子数组和的变体，要同时考虑区间长度与区间左端点；存在多个最大区间和时，保留区间长度最长的，长度相同时保留左端点最小的。
3. 编程题：给两个数组，求把第一个数组修改成非递减数组的最小代价，修改第一个数组第 i 个位置的代价是第二个数组第 i 个位置的值。

《参考解析》

最大子数组和的并列取优：把「最优」定义成有序的字典序比较。题意是三元组 (区间和, 区间长度, −左端点) 的字典序最大。实现时不要只在最后扫描一遍候选，而是在 DP 推进过程中同步维护四件事：当前段的起点、当前段的长度、全局最优的和与对应的长度、左端点。每次用 max(以 i 结尾的和) 更新全局最优时，写一个统一的比较函数（和更大者胜；和相等长度更长者胜；长度相等左端点更小者胜），避免在上百个分支里手写 if 出错。特别要注意 dp[i-1] + a[i] == a[i] 的相等分支：此时「延续上一段」与「从 i 重新开始」和相同，按题意应该延续（长度更长、左端点更小），写反了会在全零或首元素为零的用例上错。若题目规模要求更快，可以改写成前缀和：区间和等于 pre[j] − pre[i]，对固定的 j 在 i < j 中找最小的 pre[i]，同时在 pre 值相等时比较下标，用一次线性扫描配合哈希表记录「每个前缀和最早出现的下标」就能拿到最小左端点。

非递减数组最小代价：这是一道带权 LIS，不是排序题。把第 i 位改成任意值都要付 B[i] 的代价，目标是非递减。核心观察是：一定存在一组最优解，其中有一部分位置保持原值不动，这些保留下来的位置本身必须已经非递减，而未保留的位置总能被填成介于左右保留下标之间的值而不违反单调性——所以问题转化为「选一个非递减子序列保留，使其权重和最大，总代价 = 总权重 − 保留权重」。据此可以写 O(n²) 的 DP：dp[i] 表示保留第 i 个元素时前缀的最小代价，转移为 dp[i] = B[i] + min{ dp[j] }，其中 j < i 且 A[j] ≤ A[i]，同时用 dp[i] = min(dp[i], B[i] + 前缀全部改掉的代价) 处理「前面一个都不保留」的情况，最后答案是 min(dp[i] + 后缀全部改掉的代价)。值域是 0~n 时，可以用树状数组或线段树按值域维护前缀最小值，把复杂度降到 O(n log n)；如果额外要求最终数组是「严格递增」或「公差固定的等差」，条件从 A[j] ≤ A[i] 换成 A[i] − A[j] ≥ i − j 这类变形即可。

这类题的通用解法清单：值得单独整理一页。一是「区间和 + 区间属性」类：前缀和配合单调队列或哈希表，把「以 j 结尾的最优左端点」变成对 pre[i] 的极值查询。二是「改成单调 + 最小代价」类：转成带权最长非降子序列，值域小就用桶维护前缀极值，值域大就离散化加树状数组。三是「两个数组、一个改一个付代价」类：注意代价与修改量是否有关——本题只收固定代价，若代价与改动幅度成正比（如绝对值差），就变成枚举公差加加权中位数那类问题，解法完全不同。四是溢出与边界：和用 64 位、单个元素、全部相等、逆序数组这几个用例都要手跑。笔试时先把 O(n²) 的正确版本写出来保底，再考虑优化，别一上手就写线段树结果调不出来。

AI Coding 部分：反复微调不涨分时，应该停下来重新定位。评分卡在同一个数字上反复改，通常说明 AI 对题意的理解偏了，或者它改的不是评分关注的那条路径——继续让它「再优化一下」只是空转，本次就有连续几十分钟在 8324 与 8342 之间来回的情况。更有效的做法是：先把当前得分与满分之间的差距量化，找出是哪一类用例失败（格式、边界、性能、还是整体功能缺失）；再让它只解释「这个用例为什么错」，而不是直接改代码；确认原因后小步修改并立刻回归验证；如果它连续两轮改不到位，就自己接手写核心逻辑，把 AI 用在写脚手架、生成测试用例、做代码复查这些它更擅长的环节。另外 AI Coding 往往有时间和次数限制，进场先花两分钟读清评分规则与提交方式，把「能拿的分」先拿到手，再去抠细节。