LeetCode 3410 - Maximize Subarray Sum After Removing All Occurrences of One Element
We are given an integer array nums. We may perform at most one operation: 1. Choose a value x. 2. Remove every occurrence of x from the array. 3. The resulting array must remain non-empty.
Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Segment Tree
Solution
Problem Understanding
We are given an integer array nums. We may perform at most one operation:
- Choose a value
x. - Remove every occurrence of
xfrom the array. - The resulting array must remain non-empty.
After performing zero or one such operation, we compute the maximum subarray sum of the resulting array. Among all valid choices, we must return the largest possible maximum subarray sum.
The key detail is that removing a value removes all occurrences of that value, not just one occurrence. Furthermore, after removal, the remaining elements keep their original relative order and become adjacent. This means that positions formerly separated by removed values may become connected into a larger contiguous subarray.
For example, if
[-3, 2, -2, -1, 3, -2, 3]
and we remove all -2 values, we obtain
[-3, 2, -1, 3, 3]
The two 3 values become adjacent because the intervening -2 was removed.
The constraints are:
1 <= n <= 100000
-10^6 <= nums[i] <= 10^6
The array is large, so any solution that explicitly rebuilds the array for every distinct value is too slow. Since n may be 10^5, we generally need an O(n log n) or O(n) solution.
Several edge cases are important:
- The optimal answer may come from performing no deletion at all.
- All numbers may be negative.
- The array may contain only one distinct value, in which case deletion is impossible because the resulting array would be empty.
- A negative value may occur many times, and removing all of them can connect multiple positive regions into one large subarray.
- Positive values are almost never useful to remove because deleting positive contributions can only reduce candidate subarray sums.
Approaches
Brute Force
The most direct approach is to try every possible value x.
For each distinct value:
- Construct the array obtained after removing all occurrences of
x. - Run Kadane's algorithm on the resulting array.
- Track the maximum answer.
We must also consider the case of performing no deletion.
This approach is correct because it explicitly evaluates every legal operation. However, it is too slow. If there are O(n) distinct values, then rebuilding an array and running Kadane's algorithm costs O(n) per value, yielding O(n^2) total time.
With n = 100000, this is infeasible.
Key Insight
Removing a value only changes positions containing that value.
Suppose we choose a value x. Every occurrence of x effectively contributes 0 instead of x, because those elements disappear and neighboring segments become merged.
This suggests a dynamic update perspective.
Let us build a segment tree that stores the classical maximum subarray information:
- total sum
- maximum prefix sum
- maximum suffix sum
- maximum subarray sum
Initially, the tree represents the original array.
Now consider deleting a value x.
Every position whose value equals x is replaced by 0. Since deletion removes those elements and joins adjacent segments, treating them as zero contributions yields exactly the same maximum subarray behavior in the compressed array.
Therefore:
- Start with the original segment tree.
- For each distinct negative value
x, temporarily update all positions containingxfromxto0. - The root's maximum subarray sum immediately gives the answer after removing
x. - Restore the positions afterward.
Each position is updated only twice overall, once when applying its value's deletion scenario and once when restoring it.
This leads to an O(n log n) solution.
Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Rebuild array and run Kadane for every distinct value |
| Optimal | O(n log n) | O(n) | Segment tree supports efficient value-removal simulation |
Algorithm Walkthrough
Segment Tree State
For every segment we store four quantities.
Let a segment represent interval [L, R].
Its node contains:
sum, total sum of the interval.pref, maximum prefix sum.suff, maximum suffix sum.best, maximum subarray sum.
These are the standard quantities used in maximum-subarray segment trees.
Merge Formula
Given left child A and right child B:
sum = A.sum + B.sum
pref = max(A.pref, A.sum + B.pref)
suff = max(B.suff, B.sum + A.suff)
best = max(
A.best,
B.best,
A.suff + B.pref
)
The last case corresponds to the optimal subarray crossing the midpoint.
Processing
- Build a segment tree over the original array.
- Compute the answer without any deletion. This is simply the root's
best. - Group indices by value.
- Observe that removing a positive value is never beneficial. Replacing a positive number by zero cannot increase any maximum subarray sum. Therefore we only need to examine negative values.
- For a negative value
x, update every occurrence ofxin the segment tree fromxto0. - After all such updates, the root's
bestequals the maximum subarray sum after deleting all occurrences ofx. - Update the global answer.
- Restore every occurrence back to
x. - Repeat for all distinct negative values.
- Return the maximum answer found.
Why it works
For a fixed value x, deleting all occurrences of x removes their contribution while preserving the order of all remaining elements. Any subarray in the compressed array corresponds to a contiguous region in the original array whose occurrences of x contribute nothing. Replacing every occurrence of x by 0 therefore produces exactly the same set of attainable subarray sums.
The segment tree always maintains the maximum subarray sum of the current transformed array. Since we evaluate every legal negative value and also the no-deletion case, the maximum recorded value is exactly the required answer.
Python Solution
from typing import List
from collections import defaultdict
class Node:
__slots__ = ("sum", "pref", "suff", "best")
def __init__(self, total=0, pref=0, suff=0, best=0):
self.sum = total
self.pref = pref
self.suff = suff
self.best = best
class SegmentTree:
def __init__(self, nums: List[int]):
self.n = len(nums)
self.tree = [Node() for _ in range(self.n * 4)]
self.build(1, 0, self.n - 1, nums)
def merge(self, left: Node, right: Node) -> Node:
node = Node()
node.sum = left.sum + right.sum
node.pref = max(left.pref, left.sum + right.pref)
node.suff = max(right.suff, right.sum + left.suff)
node.best = max(
left.best,
right.best,
left.suff + right.pref,
)
return node
def build(self, idx: int, l: int, r: int, nums: List[int]) -> None:
if l == r:
v = nums[l]
self.tree[idx] = Node(v, v, v, v)
return
mid = (l + r) // 2
self.build(idx * 2, l, mid, nums)
self.build(idx * 2 + 1, mid + 1, r, nums)
self.tree[idx] = self.merge(
self.tree[idx * 2],
self.tree[idx * 2 + 1]
)
def update(self, idx: int, l: int, r: int, pos: int, value: int) -> None:
if l == r:
self.tree[idx] = Node(value, value, value, value)
return
mid = (l + r) // 2
if pos <= mid:
self.update(idx * 2, l, mid, pos, value)
else:
self.update(idx * 2 + 1, mid + 1, r, pos, value)
self.tree[idx] = self.merge(
self.tree[idx * 2],
self.tree[idx * 2 + 1]
)
def point_update(self, pos: int, value: int) -> None:
self.update(1, 0, self.n - 1, pos, value)
def best_sum(self) -> int:
return self.tree[1].best
class Solution:
def maxSubarraySum(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
positions = defaultdict(list)
for i, x in enumerate(nums):
positions[x].append(i)
seg = SegmentTree(nums)
answer = seg.best_sum()
for value, indices in positions.items():
if value >= 0:
continue
if len(indices) == n:
continue
for idx in indices:
seg.point_update(idx, 0)
answer = max(answer, seg.best_sum())
for idx in indices:
seg.point_update(idx, value)
return answer
The implementation begins by constructing a segment tree storing the four classical maximum-subarray quantities. The merge function implements the standard recurrence used in maximum subarray segment trees.
The dictionary positions records all indices for each value. This allows us to update every occurrence of a chosen value efficiently.
The root node always contains the maximum subarray sum of the current transformed array. For each negative value, we temporarily replace all occurrences by zero, read the root's answer, then restore the original values.
Since each point update costs O(log n) and each array position participates in only two updates overall, the total complexity remains O(n log n).
Go Solution
package main
type Node struct {
sum int64
pref int64
suff int64
best int64
}
type SegmentTree struct {
tree []Node
n int
}
func max3(a, b, c int64) int64 {
res := a
if b > res {
res = b
}
if c > res {
res = c
}
return res
}
func max2(a, b int64) int64 {
if a > b {
return a
}
return b
}
func (st *SegmentTree) merge(left, right Node) Node {
return Node{
sum: left.sum + right.sum,
pref: max2(left.pref, left.sum+right.pref),
suff: max2(right.suff, right.sum+left.suff),
best: max3(
left.best,
right.best,
left.suff+right.pref,
),
}
}
func (st *SegmentTree) build(idx, l, r int, nums []int) {
if l == r {
v := int64(nums[l])
st.tree[idx] = Node{v, v, v, v}
return
}
mid := (l + r) / 2
st.build(idx*2, l, mid, nums)
st.build(idx*2+1, mid+1, r, nums)
st.tree[idx] = st.merge(
st.tree[idx*2],
st.tree[idx*2+1],
)
}
func (st *SegmentTree) update(idx, l, r, pos int, value int64) {
if l == r {
st.tree[idx] = Node{value, value, value, value}
return
}
mid := (l + r) / 2
if pos <= mid {
st.update(idx*2, l, mid, pos, value)
} else {
st.update(idx*2+1, mid+1, r, pos, value)
}
st.tree[idx] = st.merge(
st.tree[idx*2],
st.tree[idx*2+1],
)
}
func maxSubarraySum(nums []int) int64 {
n := len(nums)
if n == 1 {
return int64(nums[0])
}
pos := map[int][]int{}
for i, v := range nums {
pos[v] = append(pos[v], i)
}
st := SegmentTree{
tree: make([]Node, 4*n),
n: n,
}
st.build(1, 0, n-1, nums)
ans := st.tree[1].best
for value, indices := range pos {
if value >= 0 {
continue
}
if len(indices) == n {
continue
}
for _, idx := range indices {
st.update(1, 0, n-1, idx, 0)
}
ans = max2(ans, st.tree[1].best)
for _, idx := range indices {
st.update(1, 0, n-1, idx, int64(value))
}
}
return ans
}
The Go implementation mirrors the Python version closely. The primary difference is the use of int64 throughout the segment tree because the maximum subarray sum may reach 10^5 × 10^6 = 10^11, which exceeds 32-bit integer limits.
Worked Examples
Example 1
Input:
[-3, 2, -2, -1, 3, -2, 3]
Initial maximum subarray:
| Subarray | Sum |
|---|---|
| [2] | 2 |
| [3] | 3 |
| [3, -2, 3] | 4 |
Therefore:
best = 4
Now examine negative values.
Remove -3
Transformed array:
[0, 2, -2, -1, 3, -2, 3]
Maximum subarray remains:
3 + (-2) + 3 = 4
Answer stays:
4
Remove -2
Transformed array:
[-3, 2, 0, -1, 3, 0, 3]
The best subarray becomes:
2 + 0 + (-1) + 3 + 0 + 3 = 7
Now:
answer = 7
Remove -1
Transformed array:
[-3, 2, -2, 0, 3, -2, 3]
Best sum:
4
No improvement.
Final answer:
7
Example 2
Input:
[1, 2, 3, 4]
Initial maximum subarray:
1 + 2 + 3 + 4 = 10
There are no negative values to consider.
Answer:
10
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Each array position is updated at most twice, each update costs O(log n) |
| Space | O(n) | Segment tree and index lists |
The segment tree contains O(n) nodes. Every occurrence of every negative value is updated once during simulation and once during restoration. Since the total number of occurrences across all values is exactly n, the total number of updates is O(n), yielding O(n log n) time.
Test Cases
sol = Solution()
assert sol.maxSubarraySum([-3, 2, -2, -1, 3, -2, 3]) == 7 # provided example
assert sol.maxSubarraySum([1, 2, 3, 4]) == 10 # no deletion needed
assert sol.maxSubarraySum([-5]) == -5 # single element
assert sol.maxSubarraySum([5]) == 5 # single positive
assert sol.maxSubarraySum([-1, -1, -1]) == -1 # cannot delete all elements
assert sol.maxSubarraySum([5, -2, 5]) == 10 # remove negative bridge
assert sol.maxSubarraySum([1, -1, 1, -1, 1]) == 3 # remove all -1 values
assert sol.maxSubarraySum([10, -5, -5, 10]) == 20 # remove repeated negative
assert sol.maxSubarraySum([0, 0, 0]) == 0 # all zeroes
assert sol.maxSubarraySum([-10, 100, -10, 100]) == 200 # join positives
assert sol.maxSubarraySum([3, -1, 2, -1, 3]) == 8 # remove all -1
assert sol.maxSubarraySum([-4, 2, -4, 2, -4]) == 4 # repeated negative value
assert sol.maxSubarraySum([1000000] * 1000) == 1000000000 # large positive sums
Test Summary
| Test | Why |
|---|---|
[-3,2,-2,-1,3,-2,3] |
Official example |
[1,2,3,4] |
No deletion optimal |
[-5] |
Single negative element |
[5] |
Single positive element |
[-1,-1,-1] |
Deletion would empty array |
[5,-2,5] |
Removing bridge negative |
[1,-1,1,-1,1] |
Multiple occurrences removed |
[10,-5,-5,10] |
Repeated negative value |
[0,0,0] |
All zeroes |
[-10,100,-10,100] |
Large gain from deletion |
[3,-1,2,-1,3] |
Joining positive segments |
[-4,2,-4,2,-4] |
Negative value appears many times |
| Large positive array | Verifies large sums and overflow safety |
Edge Cases
All Elements Equal
Consider:
[-5, -5, -5]
The only value present is -5. Removing it would leave an empty array, which is forbidden. A careless implementation might incorrectly allow this deletion and return 0.
The solution explicitly skips any value whose occurrence count equals n, guaranteeing that the resulting array remains non-empty.
All Positive Numbers
Consider:
[1, 2, 3, 4]
Deleting any positive value can only reduce potential subarray sums. The optimal answer is the sum of the entire array.
The implementation begins with the original maximum subarray sum and only evaluates negative values for deletion, preserving this optimal case automatically.
Multiple Occurrences Connecting Segments
Consider:
[10, -5, -5, 10]
Removing one occurrence is not allowed. All occurrences must disappear together.
After removing every -5, the remaining array becomes:
[10, 10]
with answer 20.
This case is easy to mishandle if one thinks in terms of deleting a single position. The implementation groups positions by value and updates every occurrence simultaneously, exactly matching the problem statement.
Sources used for verification of problem details and segment-tree approach: