##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2382.html

# 2382. Maximum Segment Sum After Removals

• Difficulty: Hard.
• Related Topics: Array, Union Find, Prefix Sum, Ordered Set.
• Similar Questions: .

## Problem

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 .
Query 4: Remove the 4th element, nums becomes [0,2,0,0,0] and the maximum segment sum is 2 for segment .
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 .
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.

## Solution

• class Solution {
private static class UF {
int[] root;
long[] sum;

public UF(int n) {
this.root = new int[n];
Arrays.fill(this.root, -1);
this.sum = new long[n];
}

public void insert(int x, int value) {
if (root[x] != -1 || sum[x] != 0) {
return;
}
this.root[x] = x;
this.sum[x] = value;
}

public int find(int x) {
while (root[x] != x) {
int fa = root[x];
int ga = root[fa];
root[x] = ga;
x = fa;
}
return x;
}

public void union(int x, int y) {
int rx = find(x);
int ry = find(y);
if (x == y) {
return;
}
root[rx] = ry;
sum[ry] += sum[rx];
}

public boolean has(int x) {
return root[x] != -1 || sum[x] != 0;
}
}

public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
int n = removeQueries.length;
long[] ret = new long[n];
long max = 0L;
UF uf = new UF(n);
for (int i = n - 1; i >= 0; i--) {
int u = removeQueries[i];
uf.insert(u, nums[u]);
for (int v = u - 1; v <= u + 1; v += 2) {
if (v >= 0 && v < n && uf.has(v)) {
uf.union(v, u);
}
}
ret[i] = max;
int ru = uf.find(u);
max = Math.max(max, uf.sum[ru]);
}
return ret;
}
}

############

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

• 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 =  * n
ans =  * 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

############

# 2382. Maximum Segment Sum After Removals
# https://leetcode.com/problems/maximum-segment-sum-after-removals/

class UnionFind:
def __init__(self):
self._parent = {}
self.segmentSum = {}
self.maxSegmentSum = 0

def merge(self, u, value):
self._parent[u] = u
self.segmentSum[u] = value
self.maxSegmentSum = max(self.maxSegmentSum, value)

if u - 1 in self._parent:
self.union(u, u - 1)

if u + 1 in self._parent:
self.union(u, u + 1)

def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b:
return

self.segmentSum[a] += self.segmentSum[b]
self._parent[b] = a
self.maxSegmentSum = max(self.maxSegmentSum, self.segmentSum[a])

def find(self, x):
if x != self._parent[x]:
self._parent[x] = self.find(self._parent[x])

return self._parent[x]

class Solution:
def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
n = len(nums)
uf = UnionFind()
res =  * n

for i in range(n - 1, -1, -1):
res[i] = uf.maxSegmentSum
u = removeQueries[i]
uf.merge(u, nums[u])

return res


• 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
}

func max(a, b int) int {
if a > b {
return a
}
return b
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).