LeetCode Solutions Blog

Maximum Segment Sum After Removals

Number: 2466

Difficulty: Hard

Paid? No

Companies: Infosys

Problem Description

Given an array of positive integers and a sequence of removal queries, each query removes an element from the array. The removal can split the array into several contiguous segments of remaining positive integers. After each removal query, the task is to determine the maximum segment sum (i.e., the sum of a contiguous block) among all segments. The twist is that the queries are applied one-by-one, and we need to output the maximum segment sum after each removal.

Key Insights

Instead of processing removals in the given order, we can reverse the process by instead "adding" elements back.
In the reverse process, initially treat the array as completely removed (all zeros) and add back elements in the reverse order of removal.
When adding an element, check its immediate neighbors. If any neighbor has already been added (i.e. belongs to a segment), merge these segments.
Use a Union Find (Disjoint Set Union) data structure to efficiently merge segments and maintain the total sum for each segment.
Keep a global variable to track the maximum segment sum seen so far.
Finally, the results obtained during the reverse simulation should be reversed to match the original order of removals.

Space and Time Complexity

Time Complexity: O(n · α(n)) ≈ O(n) per query, where n is the length of the array and α(n) is the inverse Ackermann function (almost constant). Space Complexity: O(n) for the Union Find data structure and auxiliary arrays.

Solution

We use a reverse process: start from an empty array and add elements in reverse order of removals. When an element is added, it starts as its own segment. Then check and merge with left and right neighbors (if they are already added) using the Union Find structure. The DSU keeps track of the parent, the size of the segment, and importantly the segment sum. After each addition, update the maximum sum. Finally, reverse the series of maximum sums we collected during the reverse simulation to return the answer in the order of removals.

Code Solutions

# Python solution using Union Find (DSU)
class DSU:
    def __init__(self, n, nums):
        # parent array to hold the parent representative for each index
        self.parent = list(range(n))
        # size array to union by size
        self.size = [1] * n
        # sum array to hold sum of the segment for each root
        self.segment_sum = [0] * n
        # Initially, no index is active; this will be updated when the element is added
        # nums array holds the value associated with each index
        self.nums = nums

    def find(self, i):
        # Path compression
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        # Union the segments containing indices i and j
        root_i = self.find(i)
        root_j = self.find(j)
        # If they are already in the same segment, no need to union
        if root_i == root_j:
            return
        # Merge smaller segment into larger one (union by size)
        if self.size[root_i] < self.size[root_j]:
            root_i, root_j = root_j, root_i
        self.parent[root_j] = root_i
        self.size[root_i] += self.size[root_j]
        # Update the segment sum for the root
        self.segment_sum[root_i] += self.segment_sum[root_j]
        
    def getSegmentSum(self, i):
        # Return the segment sum for the segment containing index i
        return self.segment_sum[self.find(i)]

def maximumSegmentSum(nums, removeQueries):
    n = len(nums)
    dsu = DSU(n, nums)
    # active array indicates whether an index has been added (i.e., not removed)
    active = [False] * n
    res = [0] * n
    max_sum = 0
    # Reverse simulation: start with an empty array and add elements back in the reverse order of removals.
    # answers[i] will correspond to the state BEFORE adding back the element [in reverse]
    # So we track after each addition what the maximum segment sum is.
    for i in range(n - 1, -1, -1):
        pos = removeQueries[i]
        active[pos] = True
        # When adding a new element, initialize its own segment sum.
        dsu.segment_sum[pos] = nums[pos]
        # Update max segment sum.
        max_sum = max(max_sum, nums[pos])
        # Merge with left neighbor if active
        if pos - 1 >= 0 and active[pos - 1]:
            # Before union merge, remove previous sums as they will be updated.
            dsu.union(pos, pos - 1)
            max_sum = max(max_sum, dsu.getSegmentSum(pos))
        # Merge with right neighbor if active
        if pos + 1 < n and active[pos + 1]:
            dsu.union(pos, pos + 1)
            max_sum = max(max_sum, dsu.getSegmentSum(pos))
        res[i] = max_sum
    # The answer should correspond to the state AFTER each removal happens.
    # Note: the final operation in the reverse process corresponds to no elements in the array,
    # which gives a maximum segment sum of 0.
    # Hence, we take the computed values from res.
    return res

# Example usage:
nums = [1,2,5,6,1]
removeQueries = [0,3,2,4,1]
print(maximumSegmentSum(nums, removeQueries))