leetcode 6159. 删除操作后的最大子段和 python3

输入：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] 。

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        n = len(nums)
        fa = list(range(n+1))
        sums = [0] * (n+1)
        ans = [0] * n
        def find(x):
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]
        for i in range(n-1, 0, -1):
            x = removeQueries[i]
            to = find(x+1)
            fa[x] = to
            sums[to] += sums[x] + nums[x]
            ans[i-1] = max(ans[i], sums[to])
        return ans

1. 倒着走从删除操作改为添加操作，对于子段求和会更方便。

2. find函数是一个找父节点的操作（fa的定义就是每个数的父节点都是本身），是为了后面并查集找连续子段而设置的。

3. 连接x和x+1的作用是为了在添加元素时能够很快判断出是否连续子段

to=find(x+1)：让to为x+1的父节点；fa[x]=to：让x和x+1父节点连接起来，成为了一个合并的树结构。连续的就加上数字，和原ans[i]（上一个值）比较。这部分如果看不懂可以照着例子反推一遍就懂了。

自用，题解来源：

作者：endlesscheng
链接：https://leetcode.cn/problems/maximum-segment-sum-after-removals/solution/by-endlesscheng-p61j/