Formatted question description: https://leetcode.ca/all/2382.html

2382. Maximum Segment Sum After Removals

Difficulty: Hard.
Related Topics: Array, Union Find, Prefix Sum, Ordered Set.
Similar Questions: .

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 <= 105
1 <= nums[i] <= 109
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;
    }
}

############

class Solution {
    private int[] p;
    private long[] s;

    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
        int n = nums.length;
        p = new int[n];
        s = new long[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
        long[] ans = new long[n];
        long mx = 0;
        for (int j = n - 1; j > 0; --j) {
            int i = removeQueries[j];
            s[i] = nums[i];
            if (i > 0 && s[find(i - 1)] > 0) {
                merge(i, i - 1);
            }
            if (i < n - 1 && s[find(i + 1)] > 0) {
                merge(i, i + 1);
            }
            mx = Math.max(mx, s[find(i)]);
            ans[j - 1] = mx;
        }
        return ans;
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    private void merge(int a, int b) {
        int pa = find(a), pb = find(b);
        p[pa] = pb;
        s[pb] += s[pa];
    }
}

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        def merge(a, b):
            pa, pb = find(a), find(b)
            p[pa] = pb
            s[pb] += s[pa]

        n = len(nums)
        p = list(range(n))
        s = [0] * n
        ans = [0] * n
        mx = 0
        for j in range(n - 1, 0, -1):
            i = removeQueries[j]
            s[i] = nums[i]
            if i and s[find(i - 1)]:
                merge(i, i - 1)
            if i < n - 1 and s[find(i + 1)]:
                merge(i, i + 1)
            mx = max(mx, s[find(i)])
            ans[j - 1] = mx
        return ans

############

# 2382. Maximum Segment Sum After Removals
# https://leetcode.com/problems/maximum-segment-sum-after-removals/

class UnionFind:
    def __init__(self):
        self._parent = {}
        self.segmentSum = {}
        self.maxSegmentSum = 0
    
    def merge(self, u, value):
        self._parent[u] = u
        self.segmentSum[u] = value
        self.maxSegmentSum = max(self.maxSegmentSum, value)
        
        if u - 1 in self._parent:
            self.union(u, u - 1)
        
        if u + 1 in self._parent:
            self.union(u, u + 1)
    
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return

        self.segmentSum[a] += self.segmentSum[b]
        self._parent[b] = a
        self.maxSegmentSum = max(self.maxSegmentSum, self.segmentSum[a])

    def find(self, x):
        if x != self._parent[x]:
            self._parent[x] = self.find(self._parent[x])

        return self._parent[x]

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        n = len(nums)
        uf = UnionFind()
        res = [0] * n
        
        for i in range(n - 1, -1, -1):
            res[i] = uf.maxSegmentSum
            u = removeQueries[i]
            uf.merge(u, nums[u])
        
        return res
        

using ll = long long;

class Solution {
public:
    vector<int> p;
    vector<ll> s;

    vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
        int n = nums.size();
        p.resize(n);
        for (int i = 0; i < n; ++i) p[i] = i;
        s.assign(n, 0);
        vector<ll> ans(n);
        ll mx = 0;
        for (int j = n - 1; j; --j) {
            int i = removeQueries[j];
            s[i] = nums[i];
            if (i && s[find(i - 1)]) merge(i, i - 1);
            if (i < n - 1 && s[find(i + 1)]) merge(i, i + 1);
            mx = max(mx, s[find(i)]);
            ans[j - 1] = mx;
        }
        return ans;
    }

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    void merge(int a, int b) {
        int pa = find(a), pb = find(b);
        p[pa] = pb;
        s[pb] += s[pa];
    }
};

func maximumSegmentSum(nums []int, removeQueries []int) []int64 {
	n := len(nums)
	p := make([]int, n)
	s := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	merge := func(a, b int) {
		pa, pb := find(a), find(b)
		p[pa] = pb
		s[pb] += s[pa]
	}
	mx := 0
	ans := make([]int64, n)
	for j := n - 1; j > 0; j-- {
		i := removeQueries[j]
		s[i] = nums[i]
		if i > 0 && s[find(i-1)] > 0 {
			merge(i, i-1)
		}
		if i < n-1 && s[find(i+1)] > 0 {
			merge(i, i+1)
		}
		mx = max(mx, s[find(i)])
		ans[j-1] = int64(mx)
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Explain:

nope.

Complexity:

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

2382 - Maximum Segment Sum After Removals

2382. Maximum Segment Sum After Removals

Problem

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

2382. Maximum Segment Sum After Removals

Problem

Solution

All Problems

All Solutions