LeetCode 题解工作台
删除操作后的最大子段和
给你两个下标从 0 开始的整数数组 nums 和 removeQueries ，两者长度都为 n 。对于第 i 个查询， nums 中位于下标 removeQueries[i] 处的元素被删除，将 nums 分割成更小的子段。 一个 子段 是 nums 中连续 正 整数形成的序列。 子段和 是子段中…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 并查集
答案摘要
考虑从后往前遍历数组 中的每个元素 ，用并查集来维护以 所在的连续子数组的和。 遍历过程中：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 并查集 题型思路
题目描述
给你两个下标从 0 开始的整数数组 nums 和 removeQueries ，两者长度都为 n 。对于第 i 个查询，nums 中位于下标 removeQueries[i] 处的元素被删除，将 nums 分割成更小的子段。
一个 子段 是 nums 中连续 正 整数形成的序列。子段和 是子段中所有元素的和。
请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]是第 i 次删除操作以后的 最大 子段和。
注意：一个下标至多只会被删除一次。
示例 1：
输入：nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1] 输出：[14,7,2,2,0] 解释：用 0 表示被删除的元素，答案如下所示： 查询 1 ：删除第 0 个元素，nums 变成 [0,2,5,6,1] ，最大子段和为子段 [2,5,6,1] 的和 14 。 查询 2 ：删除第 3 个元素，nums 变成 [0,2,5,0,1] ，最大子段和为子段 [2,5] 的和 7 。 查询 3 ：删除第 2 个元素，nums 变成 [0,2,0,0,1] ，最大子段和为子段 [2] 的和 2 。 查询 4 ：删除第 4 个元素，nums 变成 [0,2,0,0,0] ，最大子段和为子段 [2] 的和 2 。 查询 5 ：删除第 1 个元素，nums 变成 [0,0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。 所以，我们返回 [14,7,2,2,0] 。
示例 2：
输入：nums = [3,2,11,1], removeQueries = [3,2,1,0] 输出：[16,5,3,0] 解释：用 0 表示被删除的元素，答案如下所示： 查询 1 ：删除第 3 个元素，nums 变成 [3,2,11,0] ，最大子段和为子段 [3,2,11] 的和 16 。 查询 2 ：删除第 2 个元素，nums 变成 [3,2,0,0] ，最大子段和为子段 [3,2] 的和 5 。 查询 3 ：删除第 1 个元素，nums 变成 [3,0,0,0] ，最大子段和为子段 [3] 的和 3 。 查询 5 ：删除第 0 个元素，nums 变成 [0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。 所以，我们返回 [16,5,3,0] 。
提示：
n == nums.length == removeQueries.length1 <= n <= 1051 <= nums[i] <= 1090 <= removeQueries[i] < nremoveQueries中所有数字 互不相同 。
解题思路
方法一：逆向思维 + 并查集
考虑从后往前遍历数组 中的每个元素 ，用并查集来维护以 所在的连续子数组的和。
遍历过程中：
对于 中的每一个 ，若下标 对应的元素遍历过，可以将 与 进行合并，同理，若下标 对应的元素也遍历过了，将 与 合并。合并过程中更新连通块的元素和。
时间复杂度 。其中 是 中的元素个数。
相似题目：
class Solution:
def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def merge(a, b):
pa, pb = find(a), find(b)
p[pa] = pb
s[pb] += s[pa]
n = len(nums)
p = list(range(n))
s = [0] * n
ans = [0] * n
mx = 0
for j in range(n - 1, 0, -1):
i = removeQueries[j]
s[i] = nums[i]
if i and s[find(i - 1)]:
merge(i, i - 1)
if i < n - 1 and s[find(i + 1)]:
merge(i, i + 1)
mx = max(mx, s[find(i)])
ans[j - 1] = mx
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) due to ordered set operations and union find with path compression. Space complexity is O(n) for union find parent arrays and segment sum tracking. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to identify that brute force scanning after each removal is too slow.
- question_mark
Look for using union find or segment tree to merge contiguous segments efficiently.
- question_mark
Check if candidates handle segment sum updates correctly when neighbors are added back.
常见陷阱
外企场景- error
Failing to update segment sums correctly after merging two segments.
- error
Iterating removals in forward order causing repeated full scans of the array.
- error
Not handling edge cases when the first or last element is removed.
进阶变体
外企场景- arrow_right_alt
Compute minimum segment sum after removals instead of maximum.
- arrow_right_alt
Track the number of segments exceeding a given threshold after each removal.
- arrow_right_alt
Perform removals in batches and return the maximum segment sum after each batch.