Question

2382. Maximum Segment Sum After Removals

中文文档

Description

You are given two 0-indexed integer arrays nums and removeQueries, both of length n. For the ith query, the element in nums at the index removeQueries[i] is removed, splitting nums into different segments.

A segment is a contiguous sequence of positive integers in nums. A segment sum is the sum of every element in a segment.

Return_ an integer array _answer_, of length _n_, where _answer[i]_ is the maximum segment sum after applying the _ith _removal._

Note: The same index will not be removed more than once.

 

Example 1:

Input: nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
Output: [14,7,2,2,0]
Explanation: Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 0th element, nums becomes [0,2,5,6,1] and the maximum segment sum is 14 for segment [2,5,6,1].
Query 2: Remove the 3rd element, nums becomes [0,2,5,0,1] and the maximum segment sum is 7 for segment [2,5].
Query 3: Remove the 2nd element, nums becomes [0,2,0,0,1] and the maximum segment sum is 2 for segment [2]. 
Query 4: Remove the 4th element, nums becomes [0,2,0,0,0] and the maximum segment sum is 2 for segment [2]. 
Query 5: Remove the 1st element, nums becomes [0,0,0,0,0] and the maximum segment sum is 0, since there are no segments.
Finally, we return [14,7,2,2,0].

Example 2:

Input: nums = [3,2,11,1], removeQueries = [3,2,1,0]
Output: [16,5,3,0]
Explanation: Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 3rd element, nums becomes [3,2,11,0] and the maximum segment sum is 16 for segment [3,2,11].
Query 2: Remove the 2nd element, nums becomes [3,2,0,0] and the maximum segment sum is 5 for segment [3,2].
Query 3: Remove the 1st element, nums becomes [3,0,0,0] and the maximum segment sum is 3 for segment [3].
Query 4: Remove the 0th element, nums becomes [0,0,0,0] and the maximum segment sum is 0, since there are no segments.
Finally, we return [16,5,3,0].

 

Constraints:

• n == nums.length == removeQueries.length
• 1 <= n <= 105
• 1 <= nums[i] <= 109
• 0 <= removeQueries[i] < n
• All the values of removeQueries are unique.

Solutions

Solution 1

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
}