编程面试：删除至多一个元素后的最大子数组和

面试官考察点

给定整数数组，返回删除至多一个元素后得到的非空连续子数组最大和。删除操作最多一次，也可以不删除；删除后剩余元素仍必须来自同一个连续区间。

约束与边界

• 数组至少包含一个元素，元素可为负数、零或正数。
• 删除后不能得到空数组。
• 需要说明是否允许删除区间端点；端点删除等价于不把该元素纳入区间。
• 目标是单次扫描，不能枚举删除位置和左右区间。

把“是否删除”变成状态

维护 keep：以当前位置结尾且尚未删除元素的最大和；维护 drop：以当前位置结尾且已经删除一个元素的最大和。新元素为 x 时，keep 在“重新开始”和“延长”之间取最大值；drop 在“删除当前元素”和“延长已删除状态”之间取最大值。

区分结果状态与中间状态

答案必须同时考虑 keep 与 drop，因为最优解可能从未删除状态结束，也可能删除一个负数后结束。初始化不能把 drop 设为零，否则会允许空子数组或隐式删除不存在的元素。

解释线性复杂度

每个元素只更新两个常数状态，时间复杂度为 O(n)，额外空间为 O(1)。正确性来自状态覆盖：任意以当前位置结尾的合法区间，要么尚未删除，要么已经删除一次，且两类状态都保留了最大和。

回答前需要澄清的问题

• “删除至多一个”是否包含不删除？题目若改成必须删除，答案和单元素数组边界会改变。
• 删除后是否必须非空？若允许空数组，结果可能被错误地初始化为零。
• 输入整数是否可能溢出 32 位？这决定累加类型和测试范围。

30 秒回答框架

“我维护两个以当前位置结尾的状态：keep 表示还没删，drop 表示已经删一次。读到 x 时，keep 取重新开始或延长；drop 取删除 x 或延长旧的 drop。答案是全程 keep 与 drop 的最大值，初始化用首元素避免全负数组得到零，时间 O(n)、空间 O(1)。”

分步骤深入解答

设上一位置状态为 keepPrev 与 dropPrev。更新公式为：

keep = max(x, keepPrev + x)
drop = max(dropPrev + x, keepPrev)

第二行的 keepPrev 表示删除当前元素，旧区间至少包含一个元素；dropPrev + x 表示删除动作已经发生，再把当前元素接上。先保存旧值或使用临时变量，避免更新 keep 后污染 drop 的转移。

若数组只有一个元素，keep 是该元素，drop 不应被当作合法的空区间。实现可把 drop 初始化为负无穷，并从第二个元素开始更新；也可以在首元素上建立“未删除”和“删除首元素”的明确语义，但必须保证非空约束。

高质量示范回答

“我把问题拆成两个 DP 状态。keep 是当前下标结尾、没有删除的最大和，drop 是已经删除一个元素的最大和。对每个 x，先用旧的 keep 和 drop 计算新状态：keep=max(x, keep+x)，drop=max(drop+x, oldKeep)。全负数组不能以零初始化，因此从首元素建立状态，并返回所有状态中的最大值。每个元素只做常数次运算，复杂度 O(n) 和 O(1)。”

常见错误

• 只运行 Kadane 算法，完全没有表达删除一次的状态。
• 把 drop 初始化为 0，导致空子数组或删除虚拟元素。
• 用更新后的 keep 计算 drop，把同一个元素同时延长和删除。
• 删除后允许区间为空，却没有确认题目边界。
• 只测试正数，遗漏全负、单元素和删除端点的情况。

错误表现与修正

数组 [-5] 若返回 0，说明实现违反非空约束；数组 [1,-2,0,3] 若没有优于普通 Kadane 的结果，说明删除状态没有参与答案。修正时先写状态不变量，再用小数组逐步列出转移。

生产化实现

使用足够宽的整数类型，避免总和超出输入元素类型。若需要返回区间而非只返回和，额外保存起点、删除位置和终点元数据；状态数量仍保持常数，但比较相等值时要规定稳定的取舍规则。

验证清单

至少测试单元素、全负、全正、删除中间负数、删除端点、多个最优解和最大数值。小规模输入可用枚举删除位置加 Kadane 的 O(n²) 参考实现做随机对拍，确认线性实现的结果一致。

追问及应对

如果必须删除一个元素怎么办？

答案不能直接取 keep，因为必须使用 drop 状态；单元素数组会变成无合法非空结果，题目需要额外定义返回值或最小输入长度。

能否用前缀和解决？

前缀和可以枚举删除位置和区间，通常需要 O(n²)；若再配合左右最大子数组预处理，可达到 O(n) 但需要 O(n) 空间。两个状态的扫描方案更节省空间。

如何恢复实际区间？

为每个状态携带起点和删除下标。发生“重新开始”时重置起点，发生“删除当前”时记录当前下标；最终从最大答案状态回溯终点即可。

评分标准

• 状态定义：清楚区分未删除与已删除一次。
• 转移正确：使用旧状态，覆盖重新开始、延长与删除当前。
• 边界完整：处理全负、单元素、必须非空和整数溢出。
• 复杂度准确：达到 O(n) 时间和 O(1) 额外空间。
• 验证充分：给出枚举参考实现和覆盖边界的测试集合。

合规检查

确认状态转移、非空边界和复杂度结论在回答中保持一致。

面试作答要点

先写两个状态和不变量，再给出两条转移；强调保存旧值、首元素初始化和答案同时检查两个状态，最后说明复杂度与随机对拍。

一句话总结

允许一次删除只需在 Kadane 的连续区间状态上增加“已删除”维度，即可在线性时间、常数空间内求出非空最大和。