# Maximum Segment Sum After Removals
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-segment-sum-after-removals)
Canonical: https://scaleengineer.com/dsa/problems/maximum-segment-sum-after-removals
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Ordered Set
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## 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**.

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. For each query, we mark an element as removed and then iterate through the entire array to find all current segments and their sums, keeping track of the maximum sum.
**Time:** O(n^2). For each of the `n` queries, we iterate through the `n` elements of the array to re-calculate the maximum segment sum. · **Space:** O(n) to store the `removed` status of elements and the `answer` array.
**Pros:** Simple to understand and implement.; Follows the problem statement directly.
**Cons:** Highly inefficient for the given constraints.; Will result in a 'Time Limit Exceeded' error on competitive programming platforms.
### Explanation
The brute-force method involves a straightforward simulation of the removal process. We maintain a boolean array, say `removed`, to keep track of which elements of `nums` have been removed so far. For each query in `removeQueries`, we update this `removed` array. After each update, we perform a full scan of the `nums` array. During the scan, we calculate the sum of each contiguous segment of non-removed elements. A `currentSum` variable accumulates the sum of the current segment. Whenever we hit a removed element (or the end of the array), the current segment is terminated. We compare its sum with a `maxSum` variable, updating `maxSum` if the `currentSum` is greater. After scanning the entire array, the resulting `maxSum` is the answer for that specific query. This entire process is repeated for all `n` queries.

```java
class Solution {
    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
        int n = nums.length;
        long[] answer = new long[n];
        boolean[] removed = new boolean[n];

        for (int i = 0; i < n; i++) {
            int removeIdx = removeQueries[i];
            removed[removeIdx] = true;

            long maxSegmentSum = 0;
            long currentSegmentSum = 0;
            for (int j = 0; j < n; j++) {
                if (!removed[j]) {
                    currentSegmentSum += nums[j];
                } else {
                    maxSegmentSum = Math.max(maxSegmentSum, currentSegmentSum);
                    currentSegmentSum = 0;
                }
            }
            maxSegmentSum = Math.max(maxSegmentSum, currentSegmentSum);
            answer[i] = maxSegmentSum;
        }
        return answer;
    }
}
```
### Algorithm
- Initialize a boolean array `removed` of size `n` with all values `false`.
- Initialize a `long` array `answer` of size `n`.
- Loop through each query `i` from `0` to `n-1`:
  - Get the index to remove: `removeIdx = removeQueries[i]`.
  - Mark the index as removed: `removed[removeIdx] = true`.
  - Initialize `maxQuerySum = 0` and `currentSum = 0`.
  - Iterate through the `nums` array with index `j` from `0` to `n-1`:
    - If `removed[j]` is `false`, add `nums[j]` to `currentSum`.
    - If `removed[j]` is `true`, it signifies the end of a segment. Update `maxQuerySum = max(maxQuerySum, currentSum)` and reset `currentSum = 0`.
  - After the inner loop, update `maxQuerySum` one last time to account for a segment that might end at the last element: `maxQuerySum = max(maxQuerySum, currentSum)`.
  - Store the result for the current query: `answer[i] = maxQuerySum`.
- Return the `answer` array.

## Using TreeMap to Track Segments
This approach processes the queries in the given order. It uses a `TreeMap` to maintain the current segments. A `TreeMap` is a balanced binary search tree, which allows for efficient `O(log k)` operations, where `k` is the number of segments.
**Time:** O(n log n). Each of the `n` queries involves a few operations (like `floorEntry`, `put`, `remove`) on TreeMaps. These operations take `O(log k)` time, where `k` is the number of segments. In the worst case, `k` can be O(n). · **Space:** O(n) for the prefix sum array, the TreeMaps which can store up to O(n) segments, and the answer array.
**Pros:** Efficient enough to pass for the given constraints.; A logical way to handle dynamic splitting of segments.
**Cons:** More complex to implement due to managing multiple data structures.; Slightly less efficient than the Union-Find approach.
### Explanation
Instead of a naive scan, we can use more advanced data structures to keep track of the segments. This approach processes queries in the forward direction. We use a `TreeMap` to store the intervals of the current segments, mapping each segment's start index to its end index. To quickly find the sum of any segment, we pre-compute a prefix sum array. To efficiently find the maximum segment sum at any point, we use another `TreeMap` as a frequency map of segment sums. The largest key in this map will be our maximum sum.

For each removal query at index `q`, we first find which segment `[l, r]` contains `q`. This can be done efficiently using the `floorEntry` method of the `TreeMap`. We then remove this segment `[l, r]` and its corresponding sum from our data structures. The removal splits `[l, r]` into two new potential segments: `[l, q-1]` and `[q+1, r]`. We calculate their sums using the prefix sum array and add these new segments and their sums to our `TreeMap`s. The answer for the current query is then the largest sum present in our sum frequency map.

```java
import java.util.TreeMap;
import java.util.Map;

class Solution {
    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
        int n = nums.length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        long[] answer = new long[n];
        TreeMap<Integer, Integer> segments = new TreeMap<>();
        segments.put(0, n - 1);

        TreeMap<Long, Integer> sumCounts = new TreeMap<>();
        sumCounts.put(prefixSum[n], 1);

        for (int i = 0; i < n; i++) {
            int removeIdx = removeQueries[i];

            Map.Entry<Integer, Integer> segmentEntry = segments.floorEntry(removeIdx);
            int start = segmentEntry.getKey();
            int end = segmentEntry.getValue();
            segments.remove(start);

            long segmentSum = prefixSum[end + 1] - prefixSum[start];
            sumCounts.put(segmentSum, sumCounts.get(segmentSum) - 1);
            if (sumCounts.get(segmentSum) == 0) {
                sumCounts.remove(segmentSum);
            }

            if (removeIdx > start) {
                int newEnd = removeIdx - 1;
                segments.put(start, newEnd);
                long newSum = prefixSum[newEnd + 1] - prefixSum[start];
                sumCounts.put(newSum, sumCounts.getOrDefault(newSum, 0) + 1);
            }
            if (removeIdx < end) {
                int newStart = removeIdx + 1;
                segments.put(newStart, end);
                long newSum = prefixSum[end + 1] - prefixSum[newStart];
                sumCounts.put(newSum, sumCounts.getOrDefault(newSum, 0) + 1);
            }

            if (sumCounts.isEmpty()) {
                answer[i] = 0;
            } else {
                answer[i] = sumCounts.lastKey();
            }
        }
        return answer;
    }
}
```
### Algorithm
- Pre-calculate the prefix sums of the `nums` array to allow for O(1) range sum queries.
- Use a `TreeMap<Integer, Integer>` called `segments` to map a segment's start index to its end index.
- Use another `TreeMap<Long, Integer>` called `sumCounts` to act as a frequency map of segment sums, which allows finding the maximum sum efficiently.
- Initially, populate `segments` with one entry `{0: n-1}` and `sumCounts` with the total sum of `nums`.
- For each query `i` from `0` to `n-1`:
  - Get the removal index `q = removeQueries[i]`.
  - Find the segment `[l, r]` that contains `q` using `segments.floorEntry(q)`.
  - Remove this segment and its sum from `segments` and `sumCounts`.
  - If the left part `[l, q-1]` is a valid segment, calculate its sum using prefix sums and add it to `segments` and `sumCounts`.
  - If the right part `[q+1, r]` is a valid segment, do the same.
  - The maximum segment sum is now the largest key in `sumCounts`. If `sumCounts` is empty, the max sum is 0. Store this in `answer[i]`.
- Return `answer`.

## Union-Find on Reversed Queries
The most efficient approach involves a clever change of perspective. Instead of removing elements, we process the queries in reverse order and add elements back. This transforms the problem from splitting segments to merging segments, which is a perfect use case for the Union-Find (or Disjoint Set Union) data structure.
**Time:** O(n * α(n)), where α(n) is the extremely slow-growing inverse Ackermann function. With path compression and union by size/rank optimizations, the amortized time for Union-Find operations is nearly constant. This makes the overall time complexity effectively linear. · **Space:** O(n) for the Union-Find data structures (`parent`, `segmentSum`), the `active` array, and the `answer` array.
**Pros:** The most efficient solution with nearly linear time complexity.; Elegantly models the problem of merging segments.
**Cons:** Requires understanding of the Union-Find data structure.; The key insight of reversing the problem might not be immediately obvious.
### Explanation
This approach hinges on a key insight: processing the removals in reverse is equivalent to adding elements to an initially empty array. Adding an element can merge two existing segments or extend one. This merging process can be handled very efficiently by a Union-Find data structure.

We iterate backwards through the `removeQueries` array. We maintain a Union-Find structure where each set represents a contiguous segment of elements that are currently 'present'. We also maintain an array to store the sum of each segment, keyed by the root of the set.

For each query `i` from `n-1` down to `0`, we first record the current maximum segment sum as `answer[i]`. This is because the state before we add `removeQueries[i]` back corresponds to the state after the `i`-th removal. Then, we 'add' the element `nums[removeQueries[i]]` back. We mark its index as active. This new element initially forms a segment of its own. We then check its neighbors. If a neighbor (left or right) is already active, it means there's an adjacent segment, and we perform a `union` operation to merge the new element's segment with the neighbor's. The `union` operation also updates the segment sum. After checking both neighbors, we update the overall maximum segment sum with the sum of the newly formed (and possibly merged) segment.

```java
class Solution {
    private int[] parent;
    private long[] segmentSum;

    private int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    private void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // A simple union strategy, could be improved with union by size/rank
            if (rootI < rootJ) { // Arbitrary choice to keep smaller index as root
                parent[rootJ] = rootI;
                segmentSum[rootI] += segmentSum[rootJ];
            } else {
                parent[rootI] = rootJ;
                segmentSum[rootJ] += segmentSum[rootI];
            }
        }
    }

    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
        int n = nums.length;
        parent = new int[n];
        segmentSum = new long[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            // Initialize segmentSum with individual numbers, but they are not active yet.
        }

        long[] answer = new long[n];
        boolean[] active = new boolean[n];
        long maxSegmentSum = 0;

        for (int i = n - 1; i >= 0; i--) {
            answer[i] = maxSegmentSum;
            
            int idx = removeQueries[i];
            active[idx] = true;
            segmentSum[idx] = nums[idx]; // Activate the sum for this index

            if (idx > 0 && active[idx - 1]) {
                union(idx, idx - 1);
            }
            if (idx < n - 1 && active[idx + 1]) {
                union(idx, idx + 1);
            }
            
            int root = find(idx);
            maxSegmentSum = Math.max(maxSegmentSum, segmentSum[root]);
        }

        return answer;
    }
}
```
### Algorithm
- Initialize a Union-Find data structure for `n` elements. Each element starts in its own set.
- Create a `long` array `segmentSum` where `segmentSum[i]` will store the sum of the segment whose root is `i`. Initialize `segmentSum[i] = nums[i]`.
- Create a boolean array `active` of size `n`, initialized to `false`, to track which indices have been added back.
- Initialize `maxSegmentSum = 0` and the `answer` array.
- Iterate through the queries in reverse order, from `i = n-1` down to `0`:
  - The maximum sum *before* adding the current element is the current `maxSegmentSum`. So, `answer[i] = maxSegmentSum`.
  - Get the index to add back: `idx = removeQueries[i]`.
  - Mark this index as active: `active[idx] = true`.
  - Check the left neighbor `idx-1`. If it's active, `union(idx, idx-1)`. The `union` operation must also merge the segment sums.
  - Check the right neighbor `idx+1`. If it's active, `union(idx, idx+1)`.
  - After potential merges, the new, larger segment containing `idx` has a sum `segmentSum[find(idx)]`.
  - Update the global maximum: `maxSegmentSum = max(maxSegmentSum, segmentSum[find(idx)])`.
- Return `answer`.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
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 ]; } };
```

### Python

```python
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

```