LeetCode 2382. 删除操作后的最大子段和（Maximum Segment Sum After Removals）是一道非常适合使用 逆向思维 + 并查集（Union-Find） 解决的问题。

✅ 核心思想

- 正向删除会使数组不断分裂，难以维护最大子段和。
- 逆向思考：从最后一次删除开始，逐步“恢复”元素，相当于不断合并相邻的连续段。
- 使用 并查集 来高效合并区间，并维护每个连通块（连续子段）的和。
- 同时用一个变量（或堆）跟踪当前所有子段和的最大值。

注意：Python 中我们通常不使用堆来维护最大值（因为删除任意元素不便），而是直接记录每次合并后的新子段和，并与历史最大值比较即可。

🐍 Python3 实现（简洁、高效）

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        n = len(nums)
        
        # 并查集：parent[i] 表示 i 的根；seg_sum[i] 表示以 i 为根的连通块的和
        parent = list(range(n + 1))  # 多一位作为右边界哨兵（n 位置永不激活）
        seg_sum = [0] * (n + 1)      # 初始所有位置未激活，和为 0
        
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        # 从后往前恢复元素
        ans = [0] * n
        max_sum = 0
        
        # 逆序处理 removeQueries（最后一步删除后数组为空，ans[-1] = 0）
        for i in range(n - 1, 0, -1):
            idx = removeQueries[i]
            
            # 激活 idx：先把自己加入
            seg_sum[idx] = nums[idx]
            
            # 合并右边（idx+1）
            right_root = find(idx + 1)
            if right_root  0）
                seg_sum[idx] += seg_sum[right_root]
                parent[right_root] = idx
            
            # 合并左边（idx-1）
            if idx > 0:
                left_root = find(idx - 1)
                if seg_sum[left_root] > 0:  # 左边已激活
                    seg_sum[idx] += seg_sum[left_root]
                    parent[left_root] = idx
            
            max_sum = max(max_sum, seg_sum[idx])
            ans[i - 1] = max_sum
        
        return ans

🔁 更简洁写法（只向右合并）

利用“左邻居会在它被恢复时向右合并到当前块”的性质，可以只处理右合并：

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        n = len(nums)
        parent = list(range(n + 1))
        seg_sum = [0] * (n + 1)
        
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        ans = [0] * n
        max_sum = 0
        
        # 从后往前恢复
        for i in range(n - 1, 0, -1):
            x = removeQueries[i]
            r = find(x + 1)           # 右边连通块的根
            parent[x] = r             # x 合并到右边
            seg_sum[r] += seg_sum[x] + nums[x]  # 自动包含左边（如果 x-1 已恢复，它已合并到 x）
            max_sum = max(max_sum, seg_sum[r])
            ans[i - 1] = max_sum
        
        return ans

✅ 这个版本更短、更巧妙！  
关键在于：当 x-1 被恢复时，它会执行 parent[x-1] = find(x)，而此时 x 可能还未激活。但当我们恢复 x 时，seg_sum[x] 仍为 0（除非 x-1 已合并到 x）。  
实际上，在只向右合并的策略中，所有左边的段最终都会通过链式合并进入右边的根，所以 seg_sum[x] 在 x 被恢复前可能已经包含了左边的和！

但为了逻辑清晰，推荐第一种显式合并左右的方式，尤其在面试中更容易解释。

📌 示例

nums = [1,2,5,6,1]
removeQueries = [0,3,2,4,1]

输出: [14, 7, 2, 2, 0]

逆序恢复过程：
- 恢复索引 1 → [ ,2, , , ] → max=2
- 恢复索引 4 → [ ,2, , ,1] → max=2
- 恢复索引 2 → [ ,2,5, ,1] → max=7
- 恢复索引 3 → [ ,2,5,6,1] → max=14
- 恢复索引 0 → 全部恢复（但 ans[0] 是第一次删除后的结果，即 14）

⏱️ 复杂度

- 时间复杂度：O(n α(n)) ≈ O(n)，α 是阿克曼反函数（近乎常数）
- 空间复杂度：O(n)

✅ 总结：这道题是 逆向思维 + 并查集 的经典应用，掌握后可举一反三用于类似“动态连通性 + 区间合并”问题。