Physical Address
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.
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.length1 <= n <= 1051 <= nums[i] <= 1090 <= removeQueries[i] < n- All the values of
removeQueriesare 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[2]<=b[2])?1:-1);
TreeSet<Integer> set=new TreeSet<>();
long arr[]=new long[n],ans[]=new long[n];
set.add(-1);
set.add(n);
for(int i=0;i<n;i++){
arr[i]=nums[i];
if(i!=0) arr[i]+=arr[i-1];
}
pq.add(new long[]{0,n-1,arr[n-1]});
for(int i=0;i<n;i++){
int num=quer[i];
set.add(quer[i]);
int a=set.lower(num), b=set.higher(num);
if((a+1)<num){
pq.add(new long[]{(long)a+1,(long)num-1,arr[num-1]-(long)((a==-1)?0:arr[a])});
}
if((num+1)<b){
pq.add(new long[]{(long)num+1,(long)b-1,arr[b-1]-arr[num]});
}
while(!pq.isEmpty()){
long ab[]=pq.peek();
int s=(int) ab[0],e=(int) ab[1];
if(set.higher(s-1)>e){
ans[i]=pq.peek()[2];
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), [0], []
segments, sums = SortedList(), SortedList([0])
# compute prefix sums
for k in nums:
ps.append(ps[-1] + k)
# adding a segment - (left, right) borders and its sum
def add(l, r):
segments.add((l, r))
sums.add(ps[r + 1] - ps[l])
# 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)
add(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)
# add new segments
if left != i:
add(left, i - 1)
if i != right:
add(i + 1, 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
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 >>
