# Maximize Subarray Sum After Removing All Occurrences of One Element
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-subarray-sum-after-removing-all-occurrences-of-one-element)
Canonical: https://scaleengineer.com/dsa/problems/maximize-subarray-sum-after-removing-all-occurrences-of-one-element
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Segment Tree
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
You are given an integer array `nums`.

You can do the following operation on the array **at most** once:

* Choose **any** integer `x` such that `nums` remains **non-empty** on removing all occurrences of `x`.
* Remove **all** occurrences of `x` from the array.

Return the **maximum** subarray sum across **all** possible resulting arrays.

**Example 1:**

**Input:** nums = \[-3,2,-2,-1,3,-2,3\]

**Output:** 7

**Explanation:**

We can have the following arrays after at most one operation:

* The original array is `nums = [-3, 2, -2, -1, **3, -2, 3**]`. The maximum subarray sum is `3 + (-2) + 3 = 4`.
* Deleting all occurences of `x = -3` results in `nums = [2, -2, -1, **3, -2, 3**]`. The maximum subarray sum is `3 + (-2) + 3 = 4`.
* Deleting all occurences of `x = -2` results in `nums = [-3, **2, -1, 3, 3**]`. The maximum subarray sum is `2 + (-1) + 3 + 3 = 7`.
* Deleting all occurences of `x = -1` results in `nums = [-3, 2, -2, **3, -2, 3**]`. The maximum subarray sum is `3 + (-2) + 3 = 4`.
* Deleting all occurences of `x = 3` results in `nums = [-3, **2**, -2, -1, -2]`. The maximum subarray sum is 2.

The output is `max(4, 4, 7, 4, 2) = 7`.

**Example 2:**

**Input:** nums = \[1,2,3,4\]

**Output:** 10

**Explanation:**

It is optimal to not perform any operations.

**Constraints:**

* `1 <= nums.length <= 105`
* `-106 <= nums[i] <= 106`

# Approaches
## Iterate and Recalculate
This approach directly simulates the process described in the problem. We first identify all unique numbers in the input array. Then, for each unique number `x`, we create a new temporary array by removing all occurrences of `x`. On this new array, we calculate the maximum subarray sum using Kadane's algorithm. We keep track of the overall maximum sum found across all generated arrays, including the original array (which corresponds to not performing any operation).
**Time:** O(U * N), where N is the number of elements in `nums` and U is the number of unique elements. In the worst case, U can be equal to N, leading to an O(N^2) complexity. Finding unique elements takes O(N). The main loop runs U times. Inside the loop, creating a new array takes O(N) and Kadane's algorithm takes O(N). · **Space:** O(N) to store the unique elements and the temporary array for each unique element.
**Pros:** Simple to understand and implement as it directly follows the problem statement.; Correct for all cases.
**Cons:** Inefficient for large inputs. An O(N^2) complexity will likely time out given N can be up to 10^5.
### Explanation
The algorithm proceeds as follows:

1.  First, handle the base case of not performing any operation. Calculate the maximum subarray sum of the original `nums` array using Kadane's algorithm. This value serves as our initial answer.
2.  Find all unique elements in `nums`. A `HashSet` is suitable for this, allowing `O(n)` discovery.
3.  Iterate through each unique element `x` found in the previous step.
4.  For each `x`, check if removing it would result in an empty array. If `count(x) == nums.length`, we cannot remove `x`, so we skip it.
5.  If removing `x` is a valid operation, create a new list or array that contains all elements from `nums` except for `x`. This takes `O(n)` time.
6.  Run Kadane's algorithm on this new array to find its maximum subarray sum. Kadane's algorithm finds the maximum sum of a contiguous subarray in `O(n)` time.
7.  Compare this sum with the overall maximum sum found so far and update it if the new sum is greater.
8.  After checking all unique elements, the value stored as the overall maximum is the answer.

Here is a code snippet for this approach:
```java
import java.util.*;

class Solution {
    public long maxSubarraySum(int[] nums) {
        // Calculate max subarray sum for the original array
        long maxSoFar = kadane(nums);

        Set<Integer> uniqueNums = new HashSet<>();
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            uniqueNums.add(num);
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        for (int x : uniqueNums) {
            // Check if removing x makes the array empty
            if (counts.get(x) == nums.length) {
                continue;
            }

            List<Integer> tempList = new ArrayList<>();
            for (int num : nums) {
                if (num != x) {
                    tempList.add(num);
                }
            }
            
            int[] tempArray = tempList.stream().mapToInt(i -> i).toArray();
            maxSoFar = Math.max(maxSoFar, kadane(tempArray));
        }

        return maxSoFar;
    }

    private long kadane(int[] arr) {
        if (arr.length == 0) {
            return Long.MIN_VALUE; // Or some other indicator for empty array
        }
        long maxCurrent = arr[0];
        long maxGlobal = arr[0];
        for (int i = 1; i < arr.length; i++) {
            maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);
            if (maxCurrent > maxGlobal) {
                maxGlobal = maxCurrent;
            }
        }
        return maxGlobal;
    }
}
```
### Algorithm
- Calculate the maximum subarray sum for the original `nums` array using Kadane's algorithm and store it as the initial `global_max_sum`.
- Find all unique elements in `nums` and store them in a set.
- For each unique element `x`:
  - Check if removing all occurrences of `x` would make the array empty. If so, continue to the next unique element.
  - Create a new temporary array by filtering out all occurrences of `x` from `nums`.
  - Calculate the maximum subarray sum of the temporary array using Kadane's algorithm.
  - Update `global_max_sum = max(global_max_sum, new_max_sum)`.
- Return `global_max_sum`.

## Segment-based Calculation with Segment Tree
This approach optimizes the calculation by avoiding the explicit creation of new arrays. When we remove an element `x`, the original array is partitioned into segments separated by `x`. The new array is a concatenation of these segments. The maximum subarray sum of this concatenated sequence can be calculated efficiently if we know four properties for each segment: its total sum (S), maximum subarray sum (M), maximum prefix sum (L), and maximum suffix sum (R).
A segment tree is an ideal data structure to query these four properties for any arbitrary range `[i, j]` in `O(log N)` time. We can pre-build this segment tree on the original array. Then, for each unique element `x`, we identify the segments it creates and use the segment tree to get their properties. Finally, we combine these properties to find the maximum subarray sum for the array without `x`.
**Time:** O(N log N). Building the segment tree is O(N). Grouping indices is O(N). The main loop iterates through unique values. For a value with `k` occurrences, we perform `k+1` queries, each taking O(log N). The sum of `k` over all unique values is N. So, the total time for all queries is `sum(k_v * log N) = (sum(k_v)) * log N = N * log N`. · **Space:** O(N) for the segment tree (which requires `4N` space) and the hash map to store positions of each number.
**Pros:** Efficient and will pass the given constraints.; A generalizable technique for problems involving range queries on static arrays.
**Cons:** Significantly more complex to understand and implement compared to the brute-force approach.; Requires careful handling of edge cases like empty segments.
### Explanation
The algorithm is as follows:

1.  **Segment Tree Node:** Define a segment tree node structure to store four values for a given range: `sum`, `max_subarray_sum`, `max_prefix_sum`, and `max_suffix_sum`. All sums should be `long` to prevent overflow.
2.  **Combine Logic:** Implement a function to merge two segment tree nodes. For two adjacent ranges represented by `left` and `right` nodes, the combined node's properties are:
    *   `sum = left.sum + right.sum`
    *   `max_prefix_sum = max(left.max_prefix_sum, left.sum + right.max_prefix_sum)`
    *   `max_suffix_sum = max(right.max_suffix_sum, right.sum + left.max_suffix_sum)`
    *   `max_subarray_sum = max(left.max_subarray_sum, right.max_subarray_sum, left.max_suffix_sum + right.max_prefix_sum)`
3.  **Preprocessing:**
    *   Build the segment tree over the `nums` array in `O(N)` time.
    *   Group the indices of all occurrences for each unique number in a `HashMap<Integer, List<Integer>>`. This also takes `O(N)`.
4.  **Main Calculation:**
    *   Calculate the max subarray sum for the original array by querying the segment tree for the full range `[0, N-1]`. This is the initial `global_max_sum`.
    *   Iterate through each unique element `x` and its list of indices `p_1, p_2, ..., p_k`.
    *   If `k == N`, removing `x` is not allowed, so skip.
    *   The indices of `x` define `k+1` segments. The segments are `[0...p_1-1]`, `[p_1+1...p_2-1]`, ..., `[p_k+1...N-1]`.
    *   For each segment, query the segment tree to get its `(S, M, L, R)` properties. If a segment is empty, its properties are all 0 (or `Long.MIN_VALUE` for M, L, R if all numbers can be negative, but 0 is fine for sums).
    *   With the `k+1` sets of properties, calculate the max subarray sum for the concatenated sequence. This involves two parts:
        a. The max of all individual segment max subarray sums (`max(M_i)`).
        b. The max sum of a subarray spanning multiple segments. This can be calculated in `O(k)` time by iterating through the segments and keeping track of the best combination of a suffix from a previous segment and a prefix from the current one, including the sums of full segments in between.
    *   Update `global_max_sum` with the result for `x`.
5.  Return `global_max_sum`.

This approach reduces the complexity by efficiently querying for segment properties instead of re-computing them repeatedly.
```java
// Node for the segment tree
class Node {
    long sum, maxSum, maxPrefixSum, maxSuffixSum;
    public Node(long s, long ms, long mps, long mss) {
        sum = s; maxSum = ms; maxPrefixSum = mps; maxSuffixSum = mss;
    }
}

class Solution {
    Node[] tree;
    int[] nums;
    int n;

    // Combine two nodes
    private Node merge(Node left, Node right) {
        if (left == null) return right;
        if (right == null) return left;
        long sum = left.sum + right.sum;
        long maxPrefixSum = Math.max(left.maxPrefixSum, left.sum + right.maxPrefixSum);
        long maxSuffixSum = Math.max(right.maxSuffixSum, right.sum + left.maxSuffixSum);
        long maxSum = Math.max(left.maxSum, Math.max(right.maxSum, left.maxSuffixSum + right.maxPrefixSum));
        return new Node(sum, maxSum, maxPrefixSum, maxSuffixSum);
    }

    // Build segment tree
    private void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = new Node(nums[start], nums[start], nums[start], nums[start]);
            return;
        }
        int mid = start + (end - start) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }

    // Query segment tree
    private Node query(int node, int start, int end, int l, int r) {
        if (r < start || end < l || l > r) {
            return null; // Return a neutral element node
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = start + (end - start) / 2;
        Node p1 = query(2 * node, start, mid, l, r);
        Node p2 = query(2 * node + 1, mid + 1, end, l, r);
        return merge(p1, p2);
    }

    public long maxSubarraySum(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        if (n == 0) return 0;

        tree = new Node[4 * n];
        build(1, 0, n - 1);

        long maxAns = query(1, 0, n - 1, 0, n - 1).maxSum;

        Map<Integer, List<Integer>> positions = new HashMap<>();
        for (int i = 0; i < n; i++) {
            positions.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }

        for (Map.Entry<Integer, List<Integer>> entry : positions.entrySet()) {
            List<Integer> indices = entry.getValue();
            if (indices.size() == n) continue;

            List<Node> segments = new ArrayList<>();
            int lastIdx = -1;
            for (int idx : indices) {
                if (lastIdx + 1 <= idx - 1) {
                    segments.add(query(1, 0, n - 1, lastIdx + 1, idx - 1));
                }
                lastIdx = idx;
            }
            if (lastIdx + 1 <= n - 1) {
                segments.add(query(1, 0, n - 1, lastIdx + 1, n - 1));
            }

            if (segments.isEmpty()) continue;

            long currentMax = Long.MIN_VALUE;
            for (Node seg : segments) {
                currentMax = Math.max(currentMax, seg.maxSum);
            }

            long maxEndingHere = Long.MIN_VALUE;
            for (Node seg : segments) {
                if (maxEndingHere != Long.MIN_VALUE) {
                    currentMax = Math.max(currentMax, maxEndingHere + seg.maxPrefixSum);
                }
                maxEndingHere = Math.max(seg.maxSuffixSum, (maxEndingHere == Long.MIN_VALUE ? 0 : maxEndingHere) + seg.sum);
            }
            maxAns = Math.max(maxAns, currentMax);
        }

        return maxAns;
    }
}
```
### Algorithm
- Define a segment tree node to store `sum`, `max_subarray_sum`, `max_prefix_sum`, and `max_suffix_sum` for a range.
- Build a segment tree on the input array `nums`. This takes `O(N)`.
- Group indices by value in a hash map. `O(N)`.
- Calculate the max subarray sum for the original array (querying the full range) as the initial answer.
- For each unique value `x` with `k` occurrences:
  - If `k == N`, skip `x`.
  - Identify the `k+1` segments of the array separated by `x`.
  - For each segment, query the segment tree to get its node properties (`S, M, L, R`). This takes `O(k * log N)` total for `x`.
  - Using the properties of the segments, calculate the maximum subarray sum of their concatenation in `O(k)` time.
  - Update the overall maximum answer.
- Return the final maximum answer.