Maximum Segment Sum After Removals

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

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.

1class Solution {2    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {3        int n = nums.length;4        long[] answer = new long[n];5        boolean[] removed = new boolean[n];6 7        for (int i = 0; i < n; i++) {8            int removeIdx = removeQueries[i];9            removed[removeIdx] = true;10 11            long maxSegmentSum = 0;12            long currentSegmentSum = 0;13            for (int j = 0; j < n; j++) {14                if (!removed[j]) {15                    currentSegmentSum += nums[j];16                } else {17                    maxSegmentSum = Math.max(maxSegmentSum, currentSegmentSum);18                    currentSegmentSum = 0;19                }20            }21            maxSegmentSum = Math.max(maxSegmentSum, currentSegmentSum);22            answer[i] = maxSegmentSum;23        }24        return answer;25    }26}

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

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 TreeMaps. The answer for the current query is then the largest sum present in our sum frequency map.

1import java.util.TreeMap;2import java.util.Map;3 4class Solution {5    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {6        int n = nums.length;7        long[] prefixSum = new long[n + 1];8        for (int i = 0; i < n; i++) {9            prefixSum[i + 1] = prefixSum[i] + nums[i];10        }11 12        long[] answer = new long[n];13        TreeMap<Integer, Integer> segments = new TreeMap<>();14        segments.put(0, n - 1);15 16        TreeMap<Long, Integer> sumCounts = new TreeMap<>();17        sumCounts.put(prefixSum[n], 1);18 19        for (int i = 0; i < n; i++) {20            int removeIdx = removeQueries[i];21 22            Map.Entry<Integer, Integer> segmentEntry = segments.floorEntry(removeIdx);23            int start = segmentEntry.getKey();24            int end = segmentEntry.getValue();25            segments.remove(start);26 27            long segmentSum = prefixSum[end + 1] - prefixSum[start];28            sumCounts.put(segmentSum, sumCounts.get(segmentSum) - 1);29            if (sumCounts.get(segmentSum) == 0) {30                sumCounts.remove(segmentSum);31            }32 33            if (removeIdx > start) {34                int newEnd = removeIdx - 1;35                segments.put(start, newEnd);36                long newSum = prefixSum[newEnd + 1] - prefixSum[start];37                sumCounts.put(newSum, sumCounts.getOrDefault(newSum, 0) + 1);38            }39            if (removeIdx < end) {40                int newStart = removeIdx + 1;41                segments.put(newStart, end);42                long newSum = prefixSum[end + 1] - prefixSum[newStart];43                sumCounts.put(newSum, sumCounts.getOrDefault(newSum, 0) + 1);44            }45 46            if (sumCounts.isEmpty()) {47                answer[i] = 0;48            } else {49                answer[i] = sumCounts.lastKey();50            }51        }52        return answer;53    }54}

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

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.

1class Solution {2    private int[] parent;3    private long[] segmentSum;4 5    private int find(int i) {6        if (parent[i] == i) {7            return i;8        }9        return parent[i] = find(parent[i]);10    }11 12    private void union(int i, int j) {13        int rootI = find(i);14        int rootJ = find(j);15        if (rootI != rootJ) {16            // A simple union strategy, could be improved with union by size/rank17            if (rootI < rootJ) { // Arbitrary choice to keep smaller index as root18                parent[rootJ] = rootI;19                segmentSum[rootI] += segmentSum[rootJ];20            } else {21                parent[rootI] = rootJ;22                segmentSum[rootJ] += segmentSum[rootI];23            }24        }25    }26 27    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {28        int n = nums.length;29        parent = new int[n];30        segmentSum = new long[n];31        for (int i = 0; i < n; i++) {32            parent[i] = i;33            // Initialize segmentSum with individual numbers, but they are not active yet.34        }35 36        long[] answer = new long[n];37        boolean[] active = new boolean[n];38        long maxSegmentSum = 0;39 40        for (int i = n - 1; i >= 0; i--) {41            answer[i] = maxSegmentSum;42            43            int idx = removeQueries[i];44            active[idx] = true;45            segmentSum[idx] = nums[idx]; // Activate the sum for this index46 47            if (idx > 0 && active[idx - 1]) {48                union(idx, idx - 1);49            }50            if (idx < n - 1 && active[idx + 1]) {51                union(idx, idx + 1);52            }53            54            int root = find(idx);55            maxSegmentSum = Math.max(maxSegmentSum, segmentSum[root]);56        }57 58        return answer;59    }60}