1013携程后端笔试

《面试题目》

1. AI coding 题 1 道（原帖只记下分数 8324 与 8434，未写明题意）。
2. 编程题一：最大子数组和的变体。当存在多个最大区间和时，保留区间长度最长的；区间长度还是一样时，保留左端点最小的。
3. 编程题二：给两个数组，求把第一个数组修改成非递减数组的最小代价。修改第一个数组第 i 个位置的代价是第二个数组对应位置的值。

《参考解析》

最大子数组和变体：在 Kadane 上挂三个比较键：标准 Kadane 只维护「以当前位置结尾的最大和」，本题把状态升级成三元组 (sum, len, left)——和、区间长度、左端点。转移规则是：若「前面累加过来的和」大于 0，就延续前面的左端点；否则以当前元素重开一段（此时 left = i、len = 1）。每个位置都要参与答案比较，且比较必须是字典序：先比 sum 大，相等再比 len 大，再相等比 left 小。三个常见丢分点：一是只在全局最优更新时顺手更新，忘了并列时也要换；二是把区间长度算成 r - l（少 1）；三是用 int 存和导致溢出，数据范围大时要换 long。整个算法 O(n) 时间、O(1) 空间。

非递减数组的最小代价：状态是「值」不是「下标」：代价只与位置有关时，最优解的每个取值都能在原数组中出现过的值里找到（否则可以把该值压到最近的候选值而不破坏单调性），所以先离散化去重得到候选值集合。设 dp[i][v] 表示第 i 个位置取候选值 v 时的最小总代价，转移为 dp[i][v] = cost(i, v) + min(dp[i-1][u]) , u <= v，用前缀最小值把内层压掉就是 O(n·m)。m 很大时（n、m 都是 1e5 量级）改用树状数组或线段树按值域维护前缀最小值，复杂度降到 O(n log m)。注意两点：代价函数是「改成别的值才付代价、保持不变代价为 0」，以及答案是最后一行的最小值。这不是 LIS——把它当最长上升子序列去数「保留几个」会算错，因为每个位置的修改成本不同。

AI coding 题怎么打：这类题一般给一段描述或一段待优化代码，按要求实现并跑评测（原帖里的 8324、8434 更像评测分数），时间成本往往比两道编程题加起来还高。稳妥打法是三步：先通读全部输入输出规则和样例，写最直接、最笨但一定正确的版本把分数拿到手；然后针对评测反馈逐步优化，每次改动前保留一份已通过的代码副本；单个用例卡住不要超过总时长的三分之一，宁可放弃局部分数去保另外两题。看到分数不动但代码没改，先怀疑输入解析、边界条件（空数组、单元素、全负数）和溢出，而不是继续微调算法。

时间分配是这场最大的教训：1 道 AI coding 加 2 道编程题，实际是「三份能跑的代码」，把它当成三场小笔试来切时间，每块都留 10% 的调试余量。原帖里第一题花了一小时、第二题只剩 20 分钟直接放弃，就是前松后紧的典型。复盘建议：交卷后立刻把三题的题面、数据范围、自己的思路和卡点写下来，趁记忆还热把没做出来的题补做一遍，一周后再重做一次验证是不是真的会了——笔试的题面重复率很高，这次丢掉的分下次能直接捡回来。