2382. Maximum Segment Sum After Removals

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 [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 <= 10^5

• 1 <= nums[i] <= 10^9

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

Explain:

nope.

Complexity:

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