LeetCode Solutions Blog

Maximize Subarray Sum After Removing All Occurrences of One Element

Number: 3688

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an integer array nums, you are allowed to perform at most one operation: choose any integer x (ensuring that after removing all occurrences of x the array is non‐empty) and remove every occurrence of x from nums. After at most one such removal, return the maximum subarray sum of the resulting array. (A subarray is a contiguous subsequence of the array.)

Key Insights

Without any removal, the maximum subarray sum can be computed by using Kadane’s algorithm.
Removing a value x from the array “breaks” the array into several segments – the remaining array is the concatenation of the subarrays that exist between occurrences of x.
For a candidate x, the maximum subarray sum in the resulting array is the result of “merging” these segments optimally.
A segment tree (or any range query data structure) can be pre-built over the original nums array to answer maximum subarray sum queries over arbitrary intervals. Each candidate’s remaining segments (which are disjoint intervals) can be quickly queried and then merged (via a standard combine operation) to obtain the “global” maximum subarray sum for that candidate.
Finally, the answer is the maximum over (i) the baseline (no removal) and (ii) the value obtained after performing the removal for each candidate x (provided after removal the array isn’t empty).

Space and Time Complexity

Time Complexity: O(n log n)

Building a segment tree takes O(n).
For each candidate we perform queries over a few intervals (the total number of queries is proportional to n over all candidates) and each query takes O(log n). Space Complexity: O(n)
For the segment tree and additional dictionaries used for mapping candidates to their positions.

Solution

We solve the problem in two phases.

Compute the baseline maximum subarray sum on the original array using Kadane’s algorithm.
Preprocess the array into a segment tree. A tree node stores four values: total sum, maximum prefix sum, maximum suffix sum, and maximum subarray sum. For every distinct candidate x (that appears in nums and does not remove the entire array), obtain the list of indices where x occurs. Removing x splits the array into intervals: • From index 0 to pos[0]-1, • Between two successive occurrences, • From pos[last]+1 to the end. Use the segment tree to query each of these intervals and then “merge” the results sequentially – this mimics concatenating the segments.
The answer is the maximum value found among the baseline and each removal candidate option.

The trick is that merging the segments is done with the standard segment tree “combine” function and using the pre-built tree means that each range query is efficient rather than scanning each interval.

Code Solutions

# Python solution using a Segment Tree.
# Each node in the tree is a tuple: (total_sum, best_prefix, best_suffix, best_subarray)

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        # Size of segment tree array (using 0-indexed complete binary tree representation)
        self.tree = [None] * (4 * self.n)
        self.data = data
        self.build(0, 0, self.n - 1)
    
    def combine(self, left_node, right_node):
        # Combine two nodes into one node
        total_sum = left_node[0] + right_node[0]
        best_prefix = max(left_node[1], left_node[0] + right_node[1])
        best_suffix = max(right_node[2], right_node[0] + left_node[2])
        best_subarray = max(left_node[3], right_node[3], left_node[2] + right_node[1])
        return (total_sum, best_prefix, best_suffix, best_subarray)
    
    def build(self, index, left, right):
        if left == right:
            val = self.data[left]
            # Leaf node: total, prefix, suffix, best are all the value.
            self.tree[index] = (val, val, val, val)
            return
        mid = (left + right) // 2
        self.build(2 * index + 1, left, mid)
        self.build(2 * index + 2, mid + 1, right)
        self.tree[index] = self.combine(self.tree[2 * index + 1], self.tree[2 * index + 2])
    
    def query(self, index, left, right, ql, qr):
        # If outside range, return a neutral node which does not affect combine.
        if ql > right or qr < left:
            # For maximum subarray sum, a neutral node: total=0, but prefix, suffix, best = -infinity.
            return (0, float('-inf'), float('-inf'), float('-inf'))
        if ql <= left and right <= qr:
            return self.tree[index]
        mid = (left + right) // 2
        left_result = self.query(2 * index + 1, left, mid, ql, qr)
        right_result = self.query(2 * index + 2, mid + 1, right, ql, qr)
        return self.combine(left_result, right_result)

def kadane(nums):
    max_current = max_global = nums[0]
    for num in nums[1:]:
        max_current = max(num, max_current + num)
        max_global = max(max_global, max_current)
    return max_global

def maximize_subarray_sum(nums):
    n = len(nums)
    # baseline: no removal
    baseline = kadane(nums)

    # Map candidate value -> list of indices where it appears.
    positions = {}
    for idx, val in enumerate(nums):
        positions.setdefault(val, []).append(idx)
    
    seg_tree = SegmentTree(nums)
    best_ans = baseline

    # Consider removal for each candidate x that does not remove entire array.
    for x, idx_list in positions.items():
        if len(idx_list) == n:
            # Removing x would yield an empty array; skip.
            continue
        merged = None  # Will hold merged node for the candidate removal result.
        last = 0
        # For each contiguous interval in the array that does NOT contain x.
        for pos in idx_list:
            if last <= pos - 1:
                node = seg_tree.query(0, 0, n - 1, last, pos - 1)
                if merged is None:
                    merged = node
                else:
                    merged = seg_tree.combine(merged, node)
            last = pos + 1
        if last <= n - 1:
            node = seg_tree.query(0, 0, n - 1, last, n - 1)
            if merged is None:
                merged = node
            else:
                merged = seg_tree.combine(merged, node)
        if merged is not None:
            best_ans = max(best_ans, merged[3])
    return best_ans

# Example usage:
if __name__ == "__main__":
    # Example 1
    nums = [-3,2,-2,-1,3,-2,3]
    print(maximize_subarray_sum(nums))  # Expected output: 7
    # Example 2
    nums = [1,2,3,4]
    print(maximize_subarray_sum(nums))  # Expected output: 10