Maximum Segment Sum After Removals
HardPrompt
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] < n- All the values of
removeQueriesare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a boolean array
removedof sizenwith all valuesfalse. - Initialize a
longarrayanswerof sizen. - Loop through each query
ifrom0ton-1:- Get the index to remove:
removeIdx = removeQueries[i]. - Mark the index as removed:
removed[removeIdx] = true. - Initialize
maxQuerySum = 0andcurrentSum = 0. - Iterate through the
numsarray with indexjfrom0ton-1:- If
removed[j]isfalse, addnums[j]tocurrentSum. - If
removed[j]istrue, it signifies the end of a segment. UpdatemaxQuerySum = max(maxQuerySum, currentSum)and resetcurrentSum = 0.
- If
- After the inner loop, update
maxQuerySumone 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.
- Get the index to remove:
- Return the
answerarray.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.