Welcome to Subscribe On Youtube
2382. Maximum Segment Sum After Removals
Description
You are given two 0indexed integer arrays nums
and removeQueries
, both of length n
. For the i^{th}
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 i^{th}
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 <= 10^{5}
1 <= nums[i] <= 10^{9}
0 <= removeQueries[i] < n
 All the values of
removeQueries
are unique.
Solutions

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]; } };

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

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(i1)] > 0 { merge(i, i1) } if i < n1 && s[find(i+1)] > 0 { merge(i, i+1) } mx = max(mx, s[find(i)]) ans[j1] = int64(mx) } return ans }