千问 LeetCode 2382. 删除操作后的最大子段和 public long[] maximumSegmentSum(int[] nums, int[] removeQueries)
LeetCode 2382. 删除操作后的最大子段和 是一道典型的“逆向思维 + 并查集”题目。正向模拟删除非常困难，因为每次删除会分裂区间，难以高效维护所有子段的最大和。但如果我们从后往前逆序添加元素，就可以用并查集（Union-Find）来合并相邻的连续段，并动态维护最大子段和。
✅ 正确高效的 Java 实现
class Solution {
public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
int n = nums.length;
// parent[i] 表示 i 所在集合的根节点；sum[i] 表示以 i 为根的集合的总和
int[] parent = new int[n + 1]; // 多一位用于处理右边界
long[] sum = new long[n + 1];
// 初始化并查集：每个位置初始时未激活（sum=0），parent指向自己
for (int i = 0; i = 1; i--) {
int idx = removeQueries[i]; // 当前要恢复的位置
// 激活该位置：初始子段和为 nums[idx]
sum[idx] = nums[idx];
// 尝试与右边已激活的段合并（idx+1 到其根）
int rightRoot = find(idx + 1, parent);
if (rightRoot 0) {
int leftRoot = find(idx - 1, parent);
if (leftRoot != idx - 1 || sum[leftRoot] > 0) { // 左边已激活
sum[idx] += sum[leftRoot];
parent[leftRoot] = idx;
}
}
// 更新当前最大子段和
maxSoFar = Math.max(maxSoFar, sum[idx]);
ans[i - 1] = maxSoFar;
}
// 最后一次删除后数组全空，ans[n-1] = 0（默认值）
return ans;
}
private int find(int x, int[] parent) {
if (parent[x] != x) {
parent[x] = find(parent[x], parent);
}
return parent[x];
}
}
🧠 为什么这样写？关键点解析
1. 逆向思维（Reverse Thinking）
- 最终状态：所有元素都被删除 → 所有子段和为 0。
- 从后往前：第 n-1 次删除后 → 第 n-2 次... → 初始状态。
- 每次“恢复”一个元素，相当于合并左右已存在的连续段。
2. 并查集设计
- parent[i]：i 的父节点。
- sum[i]：仅当 i 是根节点时，sum[i] 表示该连续段的总和。
- 合并策略：
- 恢复位置 idx 时，检查 idx-1 和 idx+1 是否已被恢复（即 sum[root] > 0）。
- 将左右段的根合并到 idx（或统一合并方向，如只向右合并）。
💡 更简洁的合并方式（推荐）：
每次只将 idx 合并到 idx+1 的根，这样天然处理了右合并；左合并会在后续处理 idx-1 时自动完成（因为它会向右合并到 idx）。
这是许多题解采用的技巧，避免显式判断左右。
🔁 推荐写法（只向右合并，更简洁）
class Solution {
public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
int n = nums.length;
int[] parent = new int[n + 1];
long[] sum = new long[n + 1];
for (int i = 0; i 0; i--) {
int x = removeQueries[i];
int root = find(x + 1, parent); // 右边段的根
parent[x] = root; // x 合并到右边
sum[root] += sum[x] + nums[x]; // 累加 x 及其左边可能已合并的段
ans[i - 1] = Math.max(ans[i], sum[root]);
}
return ans;
}
private int find(int x, int[] parent) {
return parent[x] == x ? x : (parent[x] = find(parent[x], parent));
}
}
✨ 关键洞察：
- sum[x] 在 x 被恢复前为 0；若 x-1 已被恢复，则 x-1 会合并到 x（通过 x-1 向右合并），此时 sum[x] 已包含左边段的和。
- 因此 sum[root] += sum[x] + nums[x] 自动包含了 左边段 + x + 右边段 的总和！
📌 示例验证
输入：
nums = , removeQueries =
输出：
逆序恢复过程：
1. 恢复 removeQueries=1 → → max=2
2. 恢复 removeQueries=4 → → max=2
3. 恢复 removeQueries=2 → → max=7
4. 恢复 removeQueries=3 → → max=14
5. 初始状态（不恢复 removeQueries）→ ans=14
⏱️ 复杂度
- 时间：O(n α(n)) ≈ O(n)，α 是阿克曼反函数（近乎常数）。
- 空间：O(n)
此解法高效且符合 LeetCode 高分题解风格，建议掌握逆向 + 并查集的核心思想！