Question

2382. 删除操作后的最大子段和

English Version

题目描述

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

解法

方法一：逆向思维 + 并查集

考虑从后往前遍历数组 $removeQueries$ 中的每个元素 $i$，用并查集来维护以 $nums[i]$ 所在的连续子数组的和。

遍历过程中：

对于 $removeQueries$ 中的每一个 $i$，若下标 $i-1$ 对应的元素遍历过，可以将 $i-1$ 与 $i$ 进行合并，同理，若下标 $i+1$ 对应的元素也遍历过了，将 $i$ 与 $i+1$ 合并。合并过程中更新连通块的元素和。

时间复杂度 $O(nlogn)$。其中 $n$ 是 $nums$ 中的元素个数。

相似题目：

• 2334. 元素值大于变化阈值的子数组

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

class Solution {
  private int[] p;
  private long[] s;

  public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
    int n = nums.length;
    p = new int[n];
    s = new long[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    long[] ans = new long[n];
    long mx = 0;
    for (int j = n - 1; j > 0; --j) {
      int i = removeQueries[j];
      s[i] = nums[i];
      if (i > 0 && s[find(i - 1)] > 0) {
        merge(i, i - 1);
      }
      if (i < n - 1 && s[find(i + 1)] > 0) {
        merge(i, i + 1);
      }
      mx = Math.max(mx, s[find(i)]);
      ans[j - 1] = mx;
    }
    return ans;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }

  private void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    p[pa] = pb;
    s[pb] += s[pa];
  }
}

using ll = long long;

class Solution {
public:
  vector<int> p;
  vector<ll> s;

  vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
    int n = nums.size();
    p.resize(n);
    for (int i = 0; i < n; ++i) p[i] = i;
    s.assign(n, 0);
    vector<ll> ans(n);
    ll mx = 0;
    for (int j = n - 1; j; --j) {
      int i = removeQueries[j];
      s[i] = nums[i];
      if (i && s[find(i - 1)]) merge(i, i - 1);
      if (i < n - 1 && s[find(i + 1)]) merge(i, i + 1);
      mx = max(mx, s[find(i)]);
      ans[j - 1] = mx;
    }
    return ans;
  }

  int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
  }

  void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    p[pa] = pb;
    s[pb] += s[pa];
  }
};

func maximumSegmentSum(nums []int, removeQueries []int) []int64 {
  n := len(nums)
  p := make([]int, n)
  s := make([]int, n)
  for i := range p {
    p[i] = i
  }
  var find func(x int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  merge := func(a, b int) {
    pa, pb := find(a), find(b)
    p[pa] = pb
    s[pb] += s[pa]
  }
  mx := 0
  ans := make([]int64, n)
  for j := n - 1; j > 0; j-- {
    i := removeQueries[j]
    s[i] = nums[i]
    if i > 0 && s[find(i-1)] > 0 {
      merge(i, i-1)
    }
    if i < n-1 && s[find(i+1)] > 0 {
      merge(i, i+1)
    }
    mx = max(mx, s[find(i)])
    ans[j-1] = int64(mx)
  }
  return ans
}