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 [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.

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

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

Leave a Reply

Your email address will not be published.