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.length1 <= n <= 1051 <= nums[i] <= 1090 <= removeQueries[i] < nremoveQueries are unique.Problem Overview: You are given an array nums and a sequence removeQueries. After each removal, the array splits into segments of remaining elements. The task is to report the maximum segment sum after every removal.
The challenge is that removals dynamically break the array into smaller segments. Recomputing segment sums from scratch after every operation would be far too slow. Efficient solutions maintain segment boundaries and sums as elements disappear.
Approach 1: Ordered Set + Prefix Sum Simulation (O(n log n) time, O(n) space)
Precompute prefix sums so any segment sum can be calculated in constant time using prefix[r+1] - prefix[l]. Maintain current segments using an ordered structure such as a balanced tree or sorted set storing segment boundaries. When an index is removed, locate the segment containing it, split that segment into two smaller ones, and update their sums. Track the maximum segment sum with a heap or ordered structure. Each removal performs a logarithmic lookup and update, giving O(n log n) total time and O(n) space. This method relies heavily on efficient range calculations using prefix sum and boundary management with an ordered set.
Approach 2: Reverse Processing with Union-Find (O(n α(n)) time, O(n) space)
The key insight is that handling deletions directly is hard, but additions are easy. Instead of removing elements forward, process the queries in reverse and gradually add elements back. Initially all positions are inactive. When you restore an index, mark it active and merge it with active neighbors using Union Find. Each component represents a contiguous segment, and you maintain its total sum. After each activation, update the maximum segment sum. The answer for removal step i corresponds to the maximum value before the next element is restored. This approach avoids repeated splitting and instead performs efficient merges, resulting in near linear time.
Union-Find stores the parent of each index and the sum of its segment. When activating an index, check the left and right neighbors. If they are active, union the components and update the combined sum. Track the current maximum segment sum during each step.
Recommended for interviews: Reverse processing with Union-Find is the expected solution. It transforms a difficult deletion problem into a sequence of merges and achieves near O(n) performance. The ordered set simulation demonstrates understanding of segment management, but the Union-Find approach shows deeper algorithmic insight and is typically what interviewers look for in hard array problems involving dynamic segments.
This approach relies on breaking the problem into smaller subproblems, solving each one only once, and storing their solutions. This can be done using a bottom-up or top-down technique. We'll utilize memoization to optimize the recursive calls.
This C solution implements a recursive Fibonacci solver with memoization. The dp array stores results of subproblems to avoid redundant calculations.
Time Complexity: O(n)
Space Complexity: O(n)
This approach computes the result iteratively, avoiding recursion entirely. We keep track of the last two computed values, allowing us to compute the next value with constant space.
The C solution utilizes a simple loop to compute results incrementally, only storing the last two Fibonacci numbers to save space.
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n) |
| Iterative Approach | Time Complexity: O(n) |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Ordered Set + Prefix Sum | O(n log n) | O(n) | When simulating removals directly and maintaining dynamic segment boundaries |
| Reverse Processing with Union-Find | O(n α(n)) | O(n) | Optimal approach for large inputs where segments must merge efficiently |
| Naive Recompute Segments | O(n²) | O(1) | Educational baseline to understand how removals affect segments |
Biweekly Contest 85 | 2382. Maximum Segment Sum After Removals • codingMohan • 3,159 views views
Watch 3 more video solutions →Practice Maximum Segment Sum After Removals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor