删除操作后的最大子段和

难度: Hard

给你两个下标从 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.length
1 <= n <= 10⁵
1 <= nums[i] <= 10⁹
0 <= removeQueries[i] < n
removeQueries 中所有数字 互不相同 。

Submission

运行时间: 296 ms

内存: 38.1 MB

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n
        f = [0] * n
        valid_range=[-1]*n
        maxi = 0
        for i in range(n-1, 0, -1):
            x = removeQueries[i]
            l, r = x, x #  (,l) (r,)
            tot = nums[x]
            if x > 0 and valid_range[x-1] >= 0:
                tot += f[x-1]
                l = valid_range[x-1]
            if x+1 < n and valid_range[x+1] >= 0:
                tot += f[x+1]
                r = valid_range[x+1]
            # maxi = max(maxi, tot)
            f[l] = f[r] = tot
            valid_range[r] = l
            valid_range[l] = r
            res[i-1] = max(res[i],tot)

        return res

Explain

本题解采用逆向思维处理问题。初始时，所有元素都被视为删除，然后逐步添加回来，同时更新和维护子段的最大和。为了有效管理子段，使用两个数组：f记录每个子段的和，valid_range记录子段的边界。每次添加元素时，根据其左右邻居更新子段信息，合并相邻子段，并更新全局最大子段和。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n  # 存储每一步操作后的最大子段和
        f = [0] * n  # 记录每个子段的和
        valid_range = [-1] * n  # 记录每个子段的左右边界
        for i in range(n-1, 0, -1):
            x = removeQueries[i]
            l, r = x, x
            tot = nums[x]  # 初始时，当前添加的数自成一个子段
            if x > 0 and valid_range[x-1] >= 0:  # 检查左邻居是否存在有效子段
                tot += f[x-1]  # 加上左侧子段的和
                l = valid_range[x-1]  # 更新左边界
            if x+1 < n and valid_range[x+1] >= 0:  # 检查右邻居是否存在有效子段
                tot += f[x+1]  # 加上右侧子段的和
                r = valid_range[x+1]  # 更新右边界
            f[l] = f[r] = tot  # 更新子段和
            valid_range[r] = l  # 更新子段的右边界到左边界
            valid_range[l] = r  # 更新子段的左边界到右边界
            res[i-1] = max(res[i], tot)  # 记录当前最大子段和
        return res

Explore

在逆向添加元素的过程中，判断一个元素是否与其左右邻居合并依赖于邻居元素是否已经是某个有效子段的一部分。具体地，通过检查数组`valid_range`中对应位置是否有有效的边界值来判断。如果左邻居的右边界是有效的，即`valid_range[x-1] >= 0`，则该元素可以与左侧子段合并；同理，如果右邻居的左边界是有效的，即`valid_range[x+1] >= 0`，则可以与右侧子段合并。这样的判断确保了只有当前元素的直接邻居已被添加并形成了有效子段时，才考虑合并操作。

在合并子段时，更新左右边界的子段和为新计算的总和是因为合并后的新子段实际上是一个统一的整体，跨越了原来分开的各个小子段。如果只更新当前元素所在的子段，那么在未来的查询和操作中，无法正确地反映出合并后整个子段的总和。更新左右边界确保了无论从哪个端点查找子段，都能得到正确的子段总和，这对于后续操作和最大子段和的更新至关重要。

逆向处理查询，即从数组的末尾向前处理，主要是为了模拟元素逐个被添加回数组的过程。这种处理方式使问题变得更简单，因为每次添加元素时都只需要考虑当前元素与其可能的左右邻居是否形成新的子段。这样可以从一个全无元素的状态开始，逐步添加，每次操作都直接关注添加点的局部环境，避免了复杂的全局重构，从而有效维护和更新子段信息和最大子段和。

数组 `valid_range` 主要用来记录每个子段的边界信息。对于每个位置i，`valid_range[i]` 表示如果i是某个子段的一部分，这个子段的另一端的边界位置。通过更新和查询这个数组，算法可以快速地确定任何元素是否属于某个有效子段，并可以立即得知该子段的整体边界。这种快速定位边界的能力是合并子段和查询子段总和时不可或缺的，它确保了每次元素添加或合并操作都能快速准确地进行，从而高效地更新和维护子段和最大子段和。