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

约 5 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节 滴滴
标签
数组 动态规划

题目描述

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

image-20260928230244368

image-20260928230244375

题意分析

先选择一个非空连续子数组，再从里面至多删除一个元素，使剩余元素的和最大。删除可以不用，但删除后也必须至少保留一个元素，不能通过清空一个负数区间得到零。

删除内部元素会让剩余元素在原数组中出现一个缺口，这是允许的；除这一次删除之外，不能再跳过其他位置。全负数组仍应返回某个负数，长度为一时只能保留唯一元素。

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

核心思路

[!blue]

沿数组从左到右处理，用两个状态区分删除机会是否已经使用。keep 表示以当前下标结尾、完全不删除的非空子数组最大和；它必须包含当前元素。deleted 表示原区间已经处理到当前下标、恰好删除一次后的最大保留和，当前元素本身可以是被删除的那个位置。

为保证始终非空，deleted 只记录在保留了至少一个元素后发生删除的方案，不单独记录删除原区间首项的表示。后者等价于直接把子数组起点右移，且还能保留删除机会，因此由 keep 或后续删除状态覆盖，不会损失最优答案。

对于当前值 x，不删状态只有两种选择：接在旧的不删区间后面，或从当前值重新开始，所以新 keep = max(旧keep + x, x)。已删状态同样分两类：此前已经删除过一次，则必须保留当前值，得到 旧deleted + x；或者现在删除当前值，留下旧的不删区间，得到 旧keep。取两者最大即可。

计算删除当前这一分支时必须读取更新前的 keep。代码先用 prevKeep 保存它，再更新两个状态，避免拿包含当前元素的新状态表示“已经删除当前元素”。

初始只看到第一个元素时，keep 和全局答案取首值，删除状态不可达，用安全的极小值表示；不能把它初始化为零，否则会允许空结果。之后每个下标都更新全局最大值，既考虑不删，也考虑已删，因为最优区间可能在任何位置结束。

解题步骤

  1. 令 keep = arr[0]、best = arr[0]，用安全的极小值初始化不可达的 deleted。
  2. 从第二个元素开始，先把旧 keep 保存到 prevKeep。
  3. 更新不删状态为 max(旧keep + arr[i], arr[i])。
  4. 更新已删状态为 max(旧deleted + arr[i], prevKeep)。
  5. 用本轮两个状态更新全局答案，扫描结束后返回 best。

代码实现

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]);
            // 要么延续已删除状态，要么删当前值并继承旧 keep。
            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]
        }

        // 要么延续已删除状态，要么删当前值并继承旧 keep。
        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)。状态只依赖上一轮，使用几个滚动变量即可。

关键点总结

[!green]

  • keep 必须包含当前值，deleted 的原区间右端到达当前值，但当前值可能已被删除。
  • 删除当前值继承旧不删区间，继续已删区间则必须加上当前值，两类不能混用。
  • 全局答案同时考虑不删与已删，符合“至多一次”而不是“必须一次”。
  • 首值初始化与不可达删除状态共同保证最终至少保留一个元素。

易错点总结

[!yellow]

  • 把 best 或初始已删状态设成零：会让全负输入错误地选择空结果。
  • 用更新后的 keep 删除当前值：这个状态可能已经包含当前元素，必须保存上一轮的 keep。
  • 已删状态不加当前值就继续传递：等价于再次跳过一个位置，超出一次删除限制。
  • 只返回最后一个状态：最优子数组可能在更早位置结束，需要全局最大值。
  • 只考虑恰好删除一次：不删除也可能最优，长度为一时更只能保留元素。
  • 用整数最小值直接参与加法：不可达哨兵仍会加上当前值，应选择题目数值范围内不会溢出的安全极小值。

相似题目

题目 难度 关联与区别
53. 最大子数组和 中等 在Kadane状态上增加是否已删除一项的维度，子数组仍必须非空。
1493. 删掉一个元素以后全为 1 的最长子数组 中等 原题必须删除一项且元素为二进制，本题至多删除一次并最大化一般整数和。
152. 乘积最大子数组 中等 维护以当前位置结尾的最优连续区间；本题增加已经删除一次的状态，该题负数会交换最大与最小乘积状态。
918. 环形子数组的最大和 中等 维护以当前位置结尾的最优连续区间；本题增加已经删除一次的状态，该题同时计算最小区间和处理首尾相接。
1567. 乘积为正数的最长子数组长度 中等 维护以当前位置结尾的最优连续区间；本题增加已经删除一次的状态，该题只维护正负乘积对应的最长长度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/31640381
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！