# 2382. Maximum Segment Sum After Removals
###### tags: `Leetcode` `Hard` `Union Find`
Link: https://leetcode.com/problems/maximum-segment-sum-after-removals/description/
## 思路
参考[这里](https://leetcode.com/problems/maximum-segment-sum-after-removals/solutions/2454208/reverse-union-find/)
从前往后看removeQueries是一个逐渐被拆解的过程
但是从后往前看removeQueries是一个把小的group拼起来的过程 也就是union find的过程
由于```removeQueries.length==nums.length``` 最后所有的num都要被t掉
在union find的过程中我们只要keep record每一个group的sum即可 每次新来一个数字我们看它左边的数字和右边的数字是不是已经存在了 如果存在就merge起来 merge起来之后我们检查这个新的group的max和上一轮的res(上一轮的最大值就能得到答案)
## Code

class Solution {
    boolean[] exist;
    int[] fa;
    long[] sum;
    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
        int n = nums.length;
        exist = new boolean[n];
        fa = new int[n];
        sum = new long[n];
        for(int i=0; i<n; i++){
            fa[i] = i;
            sum[i] = nums[i];
        }
        long[] res = new long[n];
        for(int i=n-1; i>=1; i--){
            int j = removeQueries[i];
            exist[j]=true;
            if(j>0 && exist[j-1]) combine(j, j-1);
            if(j<n-1 && exist[j+1]) combine(j, j+1);
            res[i-1] = Math.max(res[i], sum[find(j)]);
        }
        return res;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a<b){
            fa[b]=a;
            sum[a]+=sum[b];
        }
        else{
            fa[a]=b;
            sum[b]+=sum[a];
        }
    }
}