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

• merge interval solution

c++

class Solution {
public:
    vector<long long> maximumSegmentSum(vector<int>& A, vector<int>& Q) {
        long long n = A.size(), ma = 0;
        vector<long long> l(n), r(n), sum(n), res(n);
        for(int i = 0; i < n; i++) l[i] = r[i] = i;
        for(int i = Q.size() - 1; i >= 0; i--) {
            res[i] = ma;
            sum[Q[i]] += A[Q[i]];
            int left = Q[i], right = Q[i];
            if(Q[i] + 1 < n and sum[Q[i] + 1]) {
                right = r[Q[i] + 1];
                sum[Q[i]] += sum[Q[i] + 1];
            }
            if(Q[i] - 1 >= 0 and sum[Q[i] - 1]) {
                left = l[Q[i] - 1];
                sum[Q[i]] += sum[Q[i] - 1];
            }
            r[right] = r[left] = right;
            l[right] = l[left] = left;
            sum[left] = sum[right] = sum[Q[i]];
            ma = max(ma, sum[Q[i]]);
        }
        return res;
    }
};

• heap, prefix sum, binary search solution

c++

class Solution {
    vector<long long> psum{0};
    set<int> div;
public:
    vector<long long> maximumSegmentSum(vector<int>& A, vector<int>& Q) {
        for(auto& a : A) psum.push_back(psum.back() + a);
        priority_queue<long long> heap, rm;
        div.insert(0);
        div.insert(A.size() + 1);
        heap.push(psum.back());
        vector<long long> res;
        for(auto& q : Q) {
            auto it = div.upper_bound(q);
            long long l = *prev(it), r = *it;
            long long now = psum[r - 1] - psum[l];
            rm.push(now);
            long long left = psum[q] - psum[l], right = psum[r-1] - psum[q + 1];
            if(left) heap.push(left);
            if(right) heap.push(right);
            div.insert(q + 1);
            while(!rm.empty() and rm.top() == heap.top()) {
                heap.pop();
                rm.pop();
            }
            if(!heap.empty())
                res.push_back(heap.top());
            else res.push_back(0);
        }
        return res;
    }
};