D
DevExCode

LeetCode 2382: Maximum Segment Sum After Removals Solution

Master LeetCode problem 2382 (Maximum Segment Sum After Removals), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2382. Maximum Segment Sum After Removals

Hard
ArrayUnion FindPrefix SumOrdered Set

Problem Explanation

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.

  1. Initialize a stack to store the indices of elements forming the current segment and an array segSums to store the sum of each segment.
  2. Iterate through removeQueries in reverse order.
  3. For each query, update the stack and segSums array by removing the element at the specified index and merging adjacent segments if necessary.
  4. Calculate the maximum segment sum after the removal and store it in the answer array.

Time Complexity: O(n) Space Complexity: O(n)

:

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 2382 (Maximum Segment Sum After Removals)?

This page provides optimized solutions for LeetCode problem 2382 (Maximum Segment Sum After Removals) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2382 (Maximum Segment Sum After Removals)?

The time complexity for LeetCode 2382 (Maximum Segment Sum After Removals) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2382 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2382 in Java, C++, or Python.

Back to LeetCode Solutions