LeetCode 2382: Maximum Segment Sum After Removals
Problem Description
Explanation:
To solve this problem, we can iterate through the removeQueries array in reverse order. For each query, we can calculate the maximum segment sum after removing the element at the specified index. To do this, we need to keep track of the segments in the array and their sums. We can use a stack to store the indices of elements that form the current segment.
- Initialize a stack to store the indices of elements forming the current segment and an array
segSumsto store the sum of each segment. - Iterate through
removeQueriesin reverse order. - For each query, update the stack and
segSumsarray by removing the element at the specified index and merging adjacent segments if necessary. - Calculate the maximum segment sum after the removal and store it in the
answerarray.
Time Complexity: O(n) Space Complexity: O(n)
:
Solutions
class Solution {
public int[] maxSumAfterRemoval(int[] nums, int[] removeQueries) {
int n = nums.length;
int[] answer = new int[n];
Stack<Integer> stack = new Stack<>();
int[] segSums = new int[n];
Arrays.fill(segSums, -1);
for (int i = 0; i < n; i++) {
stack.push(i);
segSums[i] = nums[i];
int left = i - 1;
int right = i + 1;
while (!stack.isEmpty() && left >= 0 && nums[left] > 0) {
segSums[i] += nums[left];
left--;
}
while (!stack.isEmpty() && right < n && nums[right] > 0) {
segSums[i] += nums[right];
right++;
}
while (stack.size() > 1 && segSums[i] > segSums[stack.peek()]) {
stack.pop();
}
}
for (int i = removeQueries.length - 1; i >= 0; i--) {
int idx = removeQueries[i];
nums[idx] = 0;
int segIdx = stack.search(idx) - 1;
int leftSum = segIdx > 0 ? segSums[stack.get(segIdx - 1)] : 0;
int rightSum = segIdx < stack.size() - 1 ? segSums[stack.get(segIdx + 1)] : 0;
int segSum = segSums[stack.get(segIdx)];
answer[i] = segSum - leftSum - rightSum;
stack.remove(segIdx);
}
return answer;
}
}Loading editor...