304 North Cardinal St.
Dorchester Center, MA 02124

# Maximum Segment Sum After Removals LeetCode Solution

## Problem – Maximum Segment Sum After Removals

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.

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.

### Maximum Segment Sum After Removals LeetCode Solution in C++

``````int find(int i, vector<long long>& ds) {
return ds[i] < 0 ? i : ds[i] = find(ds[i], ds);
}
void merge(int s1, int s2, vector<long long>& ds) {
int p1 = find(s1, ds), p2 = find(s2, ds);
ds[p2] += ds[p1];
ds[p1] = p2;
}
vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& rq) {
vector<long long> res(nums.size()), ds(nums.size(), INT_MAX);
for (int i = rq.size() - 1; i > 0; --i) {
int j = rq[i];
ds[j] = -nums[j];
if (j > 0 && ds[j - 1] != INT_MAX)
merge(j, j - 1, ds);
if (j < nums.size() - 1 && ds[j + 1] != INT_MAX)
merge(j, j + 1, ds);
res[i - 1] = max(res[i], -ds[find(j, ds)]);
}
return res;
}``````

### Maximum Segment Sum After Removals LeetCode Solution in Java

``````public long[] maximumSegmentSum(int[] nums, int[] quer) {
int n=nums.length;
PriorityQueue<long []> pq=new PriorityQueue<>((long a[],long b[])->(a<=b)?1:-1);
TreeSet<Integer> set=new TreeSet<>();
long arr[]=new long[n],ans[]=new long[n];
for(int i=0;i<n;i++){
arr[i]=nums[i];
if(i!=0) arr[i]+=arr[i-1];
}
for(int i=0;i<n;i++){
int num=quer[i];
int a=set.lower(num), b=set.higher(num);
if((a+1)<num){
}
if((num+1)<b){
}
while(!pq.isEmpty()){
long ab[]=pq.peek();
int s=(int) ab,e=(int) ab;

if(set.higher(s-1)>e){
ans[i]=pq.peek();
break;
}
else pq.remove();
}
}
return ans;
}
``````

### Maximum Segment Sum After Removals LeetCode Solution in Python

``````from sortedcontainers import SortedList

class Solution:
def maximumSegmentSum(self, nums, removeQueries):
n, ps, ans = len(nums), , []
segments, sums = SortedList(), SortedList()

# compute prefix sums
for k in nums:
ps.append(ps[-1] + k)

# adding a segment - (left, right) borders and its sum

# removing a segment
def remove(l, r):
segments.remove((l, r))
sums.remove(ps[r + 1] - ps[l])

# initial segment with borders (0, n - 1)

for i in removeQueries:
# get index of an interval containing - i
ind = segments.bisect_left((i + 1, -1)) - 1
left, right = segments[ind]

remove(left, right)
if left != i:
if i != right:

ans.append(sums[-1])
return ans
``````
##### Maximum Segment Sum After Removals LeetCode Solution Review:

In our experience, we suggest you solve this Maximum Segment Sum After Removals LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Maximum Segment Sum After Removals LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Maximum Segment Sum After Removals LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions