LeetCode 1186. 删除一次得到子数组最大和

2026-04-01 HGNULB 约 9 分钟

文章信息 8 个分类 2 个标签

分类

题目描述

✅ 1186. 删除一次得到子数组最大和

题意分析

从数组里选一段连续子数组，允许在这段里至多删掉一个元素，求剩下元素之和的最大值。删除是可选的，不删也行。

有两条约束限得很紧：删除至多一次，且删除之后剩下的部分必须非空。也就是说不能靠删光唯一的元素来得到 0，全负数组的答案一定是那个最大的负数，而不是 0。

「连续子数组」意味着候选是 $O(n^2)$ 个区间，再叠加「删哪一个」又是一层枚举，暴力是 $O(n^3)$ 或经过前缀和优化的 $O(n^2)$。数组长度上限到十万，说明必须做到线性。

删掉中间某个元素后，剩下的是左右两段连续区间的拼接，这提示答案的结构是「以某位置结尾的一段」加上「是否已经用掉删除机会」这两个信息，而不需要记住删的是哪一个。

边界包括：数组只有一个元素时只能返回它自己；全负数组时答案是最大的那个元素；删除机会没用完也算合法答案。

解法：单次删除状态动态规划

核心思路

从暴力开始。枚举左右端点得到子数组，再枚举删掉哪个元素，用前缀和可以把求和降成 $O(1)$，总体仍是 $O(n^2)$，十万的数据量下会超时。瓶颈在于大量子数组共享同一个右端点，它们的最优选择被反复重算。

回忆一下不带删除的最大子数组和（Kadane）：定义「以 i 结尾的最大子数组和」，转移是 f[i] = max(f[i-1] + a[i], a[i])，因为以 i 结尾的段要么接在以 i-1 结尾的最优段后面，要么从 i 重新开始。整个 $O(n^2)$ 的区间枚举被压成一维扫描。

本题只是多了一个二值信息：删除机会用了没有。于是把状态扩成两个：

keep 表示以当前位置结尾、且一个元素都没删的最大和；

deleted 表示以当前位置结尾、且恰好已经删掉一个元素的最大和。

keep 的转移与 Kadane 完全一致。deleted 的转移有且只有两个来源，对应「这一次删除发生在什么时候」：一是删除早已发生在前面，当前元素被保留，值为 deleted + a[i]；二是删除就发生在当前位置，也就是把 a[i] 本身丢掉，那么剩下的必须是以 i-1 结尾且未删过的那一段，值为上一轮的 keep。两者取最大即可。

这里的关键细节是「上一轮的 keep」：keep 在本轮会被覆盖，所以必须先把旧值存进 prevKeep 再更新，否则 deleted 会读到已经算进 a[i] 的新值，等于既保留又删除了同一个元素。

由此得到的不变量是：每轮循环结束时，keep 与 deleted 分别是「以下标 i 结尾、未删/已删一个元素」的最大和，且两者对应的子数组都非空。deleted 的初值取一个极小值（而不是 0），正是为了表达「第一个元素之前不可能已经删过东西」这种不可达状态；用 Integer.MIN_VALUE / 2 而不是 Integer.MIN_VALUE，是为了让后续的 deleted + a[i] 不会溢出。

答案是所有位置上两个状态的最大值，因为最优子数组必然以某个下标结尾。

解题步骤

初始化 keep = arr[0]：以第 0 位结尾且不删元素的段只能是 [arr[0]] 本身。

初始化 deleted 为极小值：以第 0 位结尾又要删掉一个元素，只能删掉 arr[0] 自己，那样子数组就空了，不合法，所以标成不可达。用 MIN_VALUE / 2 留出加法余量，避免下一轮相加时下溢成正数。

初始化 best = arr[0]，保证答案至少有一个合法候选，也顺便处理了数组长度为 1 的情形。

从下标 1 开始遍历，每轮第一件事是 prevKeep = keep，把上一位置的未删除状态存下来。顺序错了整个转移就废了。

更新 keep = max(keep + arr[i], arr[i])：要么延长前面的段，要么以当前元素另起一段。

更新 deleted = max(deleted + arr[i], prevKeep)：前者是「删除早已发生、保留当前元素」，后者是「此刻删掉当前元素、沿用上一位置未删的段」。注意第二项不加 arr[i]，因为它正是被删掉的那个。

用 keep 与 deleted 更新 best。每一轮都要更新，因为最优段可能在任何位置结束。

遍历结束返回 best。

以 arr = [1,-2,0,3] 走一遍。初始 keep = 1、deleted = 极小、best = 1。

i = 1，arr[1] = -2：先存 prevKeep = 1。keep = max(1 + (-2), -2) = -1，即段 [1,-2] 优于 [-2]。deleted = max(极小 + (-2), 1) = 1，含义是「删掉 -2，保留前面的 [1]」。best = max(1, -1, 1) = 1。

i = 2，arr[2] = 0：prevKeep = -1。keep = max(-1 + 0, 0) = 0，从当前元素重开更优。deleted = max(1 + 0, -1) = 1，含义仍是「删掉 -2」，对应段 [1,-2,0] 删去 -2 得和 1。best 仍为 1。

i = 3，arr[3] = 3：prevKeep = 0。keep = max(0 + 3, 3) = 3，对应段 [0,3] 或 [3]。deleted = max(1 + 3, 0) = 4，取的是第一项，含义是「之前删掉了 -2，现在把 3 接上」，对应段 [1,-2,0,3] 删去 -2 得 1 + 0 + 3 = 4。best = max(1, 3, 4) = 4。

返回 4，与题目样例一致。注意 i = 3 那步如果误用了本轮更新后的 keep（即 3）而不是 prevKeep（即 0），deleted 会算成 max(4, 3) = 4 恰好没错，但在 arr = [1,-2,3] 上就会算出 deleted = max(极小, 3) = 3，而正确值是删掉 -2 得 4，答案立刻偏小。

再验证全负用例 arr = [-1,-1,-1]：初始 keep = -1、best = -1。i = 1 时 keep = max(-2,-1) = -1，deleted = max(极小-1, -1) = -1；i = 2 同理。返回 -1，正确——删掉一个元素后剩下的段仍非空，不能返回 0。

代码实现

class Solution {
    public int maximumSum(int[] arr) {
        int keep = arr[0];
        int deleted = Integer.MIN_VALUE / 2;
        int best = arr[0];

        for (int i = 1; i < arr.length; i++) {
            int prevKeep = keep;

            keep = Math.max(keep + arr[i], arr[i]);
            deleted = Math.max(deleted + arr[i], prevKeep);
            best = Math.max(best, Math.max(keep, deleted));
        }

        return best;
    }
}

func maximumSum(arr []int) int {
    keep := arr[0]
    deleted := -1 << 30
    best := arr[0]

    for i := 1; i < len(arr); i++ {
        prevKeep := keep

        if keep+arr[i] > arr[i] {
            keep = keep + arr[i]
        } else {
            keep = arr[i]
        }

        if deleted+arr[i] > prevKeep {
            deleted = deleted + arr[i]
        } else {
            deleted = prevKeep
        }

        if keep > best {
            best = keep
        }
        if deleted > best {
            best = deleted
        }
    }

    return best
}

复杂度分析

时间复杂度：$O(n)$，只做一趟扫描，每个位置上做常数次比较与加法。

空间复杂度：$O(1)$，两个状态都被压成滚动变量，不需要保存整张 DP 表；若写成 dp[i][2] 的二维形式则是 $O(n)$。

关键点总结

Kadane 的本质是「以 i 结尾」的状态定义，它把 $O(n^2)$ 的区间枚举压成线性；遇到任何「连续子数组 + 附加限制」的题，先套这个定义再考虑加维度。

附加限制是二值的（用没用过某次操作）时，直接把状态翻倍即可，转移按「这次操作发生在过去还是发生在当下」拆成两项，这套拆法可以推广到「至多删 k 个」的 dp[i][j]。

滚动变量更新有先后依赖时，必须显式保存上一轮的旧值；「先算谁后算谁」的顺序问题是这类压缩写法最高频的 bug。

不可达状态要用极小值而不是 0 来表示，否则会凭空造出一个「和为 0 的空子数组」这种非法候选；同时要留足加法余量防止溢出。

面试视角：面试官会先让你写 53 题的 Kadane，再加上「可以删一个」的条件观察你能否自然地扩状态。答完之后主动补两点会加分——一是解释为什么答案不能是 0（子数组非空），二是给出等价的「前后缀分解」解法：枚举被删元素 i，答案为「以 i-1 结尾的最大和」加「以 i+1 开头的最大和」，同样线性但需要两个数组。

易错点总结

错误写法：更新 deleted 时用本轮新的 keep 而不是 prevKeep → 用例 arr = [1,-2,3]，deleted 被算成 3，正确答案是删掉 -2 得 4。

错误写法：deleted 初始化为 0 → 用例 arr = [-1,-1,-1]，第一轮 deleted = max(0-1, -1) = -1 看似正常，但用例 arr = [-5] 之外的全负数组里，0 会被当作合法的空子数组候选混入 best，返回 0，正确答案是 -1。

错误写法：deleted 初始化为 Integer.MIN_VALUE → 用例 arr = [-1,-1]，第一轮 deleted + arr[1] 直接下溢成一个极大正数，返回值变成 2147483646 级别的垃圾数。

错误写法：deleted 的第二个来源写成 prevKeep + arr[i] → 用例 arr = [1,-2,0,3]，被删的元素又被加了回来，退化成不删的情况，返回 3 而不是 4。

错误写法：best 初始化为 0 → 用例 arr = [-1,-1,-1]，返回 0，正确答案是 -1；子数组必须非空这一条被违反。

错误写法：best 只用 keep 更新而漏掉 deleted → 用例 arr = [1,-2,0,3]，返回 3，正确答案是 4。

错误写法：循环从 i = 0 开始且状态在循环内初始化 → 用例 arr = [5]，第 0 位会执行一次「删掉自己」的转移，deleted 变成 0 并被计入答案，返回 5 虽然对，但 arr = [-5] 时会返回 0，正确答案是 -5。

错误写法：把 keep 的转移写成 keep += arr[i] 而不取 max → 用例 arr = [-10, 5]，累积的负前缀没被丢掉，keep 变成 -5，返回 -5，正确答案是 5。

错误写法：认为 deleted 可以对应空子数组，于是加一句 deleted = Math.max(deleted, 0) → 用例 arr = [-2,-3]，返回 0，正确答案是 -2。

错误写法：写成允许连续跳过多个元素的转移 deleted = max(deleted + arr[i], prevKeep, deleted) → 用例 arr = [1,-2,-3,4]，-2 和 -3 被一起跳过，返回 5，正确答案是 4。

错误写法：假设答案一定用掉删除机会，最后只返回 deleted 的最大值 → 用例 arr = [1,2,3]，返回删掉一个元素后的 5，正确答案是不删的 6。

相似题目

题目	难度	考察点
53. 最大子数组和	中等	最基础的 Kadane，没有附加状态，可作为本题的骨架
918. 环形子数组的最大和	中等	首尾相接，需要用总和减去最小子数组和处理跨界情形
152. 乘积最大子数组	中等	乘法下负负得正，必须同时维护最大与最小两个状态
1191. K 次串联后最大子数组之和	中等	数组重复 k 次，要按整段和的正负分类讨论并取模
剑指 Offer 42. 连续子数组的最大和	简单	53 的中文版，适合先在此确认全负数组的边界处理
面试题 16.17. 连续数列	简单	同为 Kadane 裸题，可用来练滚动变量与前缀和两种写法的对照