10.13 携程笔试：最大子数组和变体、等差数列最小代价与 AI Coding

《面试题目》

1. 编程题：最大连续子数组和，要求输出最大值、区间长度范围与初始索引；存在多个和最大的区间时，取区间长度最长的；长度也相同时，取左端点最小的。
2. 编程题：给定两个数组 A 和 B，A 记录一串值，要求把 A 改成一个单调不递减的等差数列，B 记录修改 A 每一位所需的代价，数组长度为 n，A 中值的大小范围在 0~n，求最小代价。
3. AI Coding 题：从初始用例 8 2 3 5 出发，通过与 AI 多轮交互把它改到 8 4 4 5。

《参考解析》

最大子数组和变体：Kadane 打底，并列取优要显式定义比较顺序。基础做法是 dp[i] = max(a[i], dp[i-1] + a[i])，过程中记录全局最大值。本题的难点在于「和相同」时的第二、第三关键字：先取区间长度更长，长度再相同取左端点更小。稳妥的实现是在 DP 里同时维护当前区间的左端点与长度，并在更新全局最优时写一个比较函数，优先级依次为「和更大 → 长度更长 → 左端点更小」，注意当 dp[i-1] + a[i] == a[i] 这类相等情况时，按「起点更靠左且长度更长」的原则选择延续上一段还是重新开始，否则会在全为 0 或全为负数的用例上出错。另一个必须主动检查的点是数据范围与溢出：区间和的累加很容易超出 int，用 long long 承接。这场笔试里作者正是因为用 int 记和，一直只有 16% 的通过率，换成 long 就过了——笔试中遇到「小数据能过、大数据全挂」，第一反应就该是溢出与边界，而不是怀疑算法逻辑。

等差数列最小代价：枚举公差，把「选首项」化成加权中位数问题。目标数组形如 c + i·d（i 从 0 开始，d ≥ 0 才算单调不递减）。思路是枚举公差 d（因为 A 中值域是 0n，d 也只需枚举 0n），此时每个位置的目标值是首项 c 的一次函数，代价为 Σ B[i] · |A[i] − (c + i·d)|，这是关于 c 的凸函数，最小值在加权中位数处取得——把每个位置的「虚拟取值」A[i] − i·d 按权重 B[i] 排序，取加权累计过半的那个值作为 c 即可，整体复杂度 O(n² log n)，在 n 不太大时足够。这个「枚举参数 + 加权中位数」的套路也出现在「把数组改成非递减」「带权绝对偏差最小化」一类题里，值得单独记下来。如果 n 很大导致 O(n² log n) 超时，可以再考虑 d 的候选只需落在若干相邻元素的差值附近，或改用斜率优化与凸包，但笔试阶段先把能过 100% 的分层解写出来更实际。

AI Coding 题：把它当成「带验收标准的工程协作」，而不是许愿。这类题的评测通常是固定的一组隐藏用例，所以策略是先把接口契约固定下来——函数名、入参出参结构、边界约定，让 AI 只在这个壳里改实现，不要让它顺手改配置文件和测试脚手架；本次就有 AI 一直在改 JSON、测试文件也没改好，白白消耗时间。有效流程是：先让它复述题意与约束，确认理解一致；再让它输出最小改动方案；然后立刻用给定样例验证，失败就把「输入、期望输出、实际输出」三件事一起喂回去，而不是只说「还是不对」；多次无进展就回滚到上一个能过的版本重新描述问题，别在错误的分支上继续叠改动。时间分配上，先把两道编程题的容易分拿到（哪怕暴力骗分），再回头和 AI 磨最后的差距，避免卡在一道题上把其他题的时间吃光。