Maximize Subarray Sum After Removing All Occurrences of One Element - Solution & Explanation

Problem Overview: You get an integer array nums. Pick exactly one value x and remove all its occurrences from the array. After the removal, the array closes the gaps. Your goal is to compute the maximum possible subarray sum in the resulting array.

Approach 1: Try Removing Each Value + Kadane (O(n * u) time, O(1) space)

The most direct approach is to simulate the operation for every distinct value in the array. For a candidate value x, iterate through the array and skip all elements equal to x. While scanning the remaining elements, run Kadane’s algorithm to compute the maximum subarray sum. Repeat this process for every unique value u. This approach clearly demonstrates the problem mechanics but becomes slow when the array contains many distinct values because the entire array is scanned repeatedly.

Approach 2: Segment Tree with Temporary Updates (O(n log n) time, O(n) space)

A more scalable strategy uses a segment tree that stores the standard maximum subarray metrics: sum, maxPrefix, maxSuffix, and maxSubarray. First build the tree over the original array. Then group indices by value. For a value x, temporarily update all its positions in the tree to 0, which simulates removing those elements while allowing adjacent segments to merge. After applying these updates, the root node immediately gives the maximum subarray sum of the modified array. Record the result, then revert the updates before testing the next value.

This works because replacing removed elements with 0 preserves continuity of the subarray while eliminating their contribution. The segment tree recomputes prefix/suffix merges in O(log n) per update, making the total cost proportional to the number of elements processed.

Recommended for interviews: Interviewers typically expect a solution that avoids recomputing Kadane for every value. Explaining the brute force approach shows you understand the effect of removing a value. Implementing the optimized version with a segment tree and concepts from dynamic programming demonstrates stronger algorithmic thinking and reduces the complexity to O(n log n).