Maximum Segment Sum After Removals — LeetCode 2382 Python Solution

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

Example

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:

Python solution

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

Complexity

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2382. Maximum Segment Sum After Removals is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Union Find.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Related problems