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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4

Input: nums = [1,2,3,4]
Output: 10
Explanation:
It is optimal to not perform any operations.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^6 <= nums[i] <= 10^6

Examples

Solution

Method 1 – Prefix Sum and Hash Map

Intuition

To maximize the subarray sum after removing all occurrences of one element, try removing each unique element and compute the maximum subarray sum of the remaining array. Use prefix sums and a hash map to efficiently compute the result for each candidate.

Approach

  1. For each unique value in nums, create a new array with all its occurrences removed.
  2. For each such array, use Kadane’s algorithm to find the maximum subarray sum.
  3. Track the maximum sum found across all possible removals (including the case where no element is removed).
  4. Return the maximum sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int maxSumAfterRemoval(vector<int>& nums) {
        unordered_set<int> vals(nums.begin(), nums.end());
        int ans = INT_MIN;
        for (int v : vals) {
            int cur = 0, best = INT_MIN;
            for (int x : nums) {
                if (x == v) continue;
                cur = max(x, cur + x);
                best = max(best, cur);
            }
            ans = max(ans, best);
        }
        // Also consider not removing anything
        int cur = 0, best = INT_MIN;
        for (int x : nums) {
            cur = max(x, cur + x);
            best = max(best, cur);
        }
        ans = max(ans, best);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int maxSumAfterRemoval(int[] nums) {
        Set<Integer> vals = new HashSet<>();
        for (int x : nums) vals.add(x);
        int ans = Integer.MIN_VALUE;
        for (int v : vals) {
            int cur = 0, best = Integer.MIN_VALUE;
            for (int x : nums) {
                if (x == v) continue;
                cur = Math.max(x, cur + x);
                best = Math.max(best, cur);
            }
            ans = Math.max(ans, best);
        }
        // Also consider not removing anything
        int cur = 0, best = Integer.MIN_VALUE;
        for (int x : nums) {
            cur = Math.max(x, cur + x);
            best = Math.max(best, cur);
        }
        ans = Math.max(ans, best);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maxSumAfterRemoval(self, nums: list[int]) -> int:
        vals = set(nums)
        ans = float('-inf')
        for v in vals:
            cur = best = float('-inf')
            for x in nums:
                if x == v:
                    cur = float('-inf')
                else:
                    cur = x if cur == float('-inf') else max(x, cur + x)
                    best = max(best, cur)
            ans = max(ans, best)
        # Also consider not removing anything
        cur = best = float('-inf')
        for x in nums:
            cur = x if cur == float('-inf') else max(x, cur + x)
            best = max(best, cur)
        ans = max(ans, best)
        return ans

Complexity

  • ⏰ Time complexity: O(n^2) — for each unique value, we scan the array.
  • 🧺 Space complexity: O(n) — for storing unique values and variables.