3410. Maximize Subarray Sum After Removing All Occurrences of One Element LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3410. Maximize Subarray Sum After Removing All Occurrences of One Element LeetCode Solution with the best time and space complexity. The solution to Maximize Subarray Sum After Removing All Occurrences of One Element problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Maximize Subarray Sum After Removing All Occurrences of One Element solution in C++
  4. Maximize Subarray Sum After Removing All Occurrences of One Element solution in Java
  5. Maximize Subarray Sum After Removing All Occurrences of One Element solution in Python
  6. Additional Resources
3410. Maximize Subarray Sum After Removing All Occurrences of One Element LeetCode Solution image

Problem Statement of Maximize Subarray Sum After Removing All Occurrences of One Element

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

Complexity Analysis

  • Time Complexity: O(n\log n)
  • Space Complexity: O(n)

3410. Maximize Subarray Sum After Removing All Occurrences of One Element LeetCode Solution in C++

// Same as 53. Maximum Subarray
struct T {
  long sum;
  long maxSubarraySumPrefix;
  long maxSubarraySumSuffix;
  long maxSubarraySum;
  T() = default;
  T(int num)
      : sum(num),
        maxSubarraySumPrefix(num),
        maxSubarraySumSuffix(num),
        maxSubarraySum(num) {}
  T(long sum, long prefix, long suffix, long maxSum)
      : sum(sum),
        maxSubarraySumPrefix(prefix),
        maxSubarraySumSuffix(suffix),
        maxSubarraySum(maxSum) {}
};

class SegmentTree {
 public:
  SegmentTree(const vector<int>& nums) : n(nums.size()), tree(nums.size() * 4) {
    build(nums, 0, 0, n - 1);
  }

  // Updates nums[i] to val.
  void update(int i, int val) {
    update(0, 0, n - 1, i, val);
  }

  long getMaxSubarraySum() const {
    return tree[0].maxSubarraySum;
  }

 private:
  const int n;     // the size of the input array
  vector<T> tree;  // the segment tree

  void build(const vector<int>& nums, int treeIndex, int lo, int hi) {
    if (lo == hi) {
      tree[treeIndex] = T(nums[lo]);
      return;
    }
    const int mid = (lo + hi) / 2;
    build(nums, 2 * treeIndex + 1, lo, mid);
    build(nums, 2 * treeIndex + 2, mid + 1, hi);
    tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
  }

  void update(int treeIndex, int lo, int hi, int i, int val) {
    if (lo == hi) {
      tree[treeIndex] = T(val);
      return;
    }
    const int mid = (lo + hi) / 2;
    if (i <= mid)
      update(2 * treeIndex + 1, lo, mid, i, val);
    else
      update(2 * treeIndex + 2, mid + 1, hi, i, val);
    tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
  }

  T merge(const T& left, const T& right) const {
    return T(
        left.sum + right.sum,
        max(left.maxSubarraySumPrefix, left.sum + right.maxSubarraySumPrefix),
        max(right.maxSubarraySumSuffix, right.sum + left.maxSubarraySumSuffix),
        max({left.maxSubarraySum, right.maxSubarraySum,
             left.maxSubarraySumSuffix + right.maxSubarraySumPrefix}));
  }
};

class Solution {
 public:
  long long maxSubarraySum(vector<int>& nums) {
    const bool allPositives =
        ranges::all_of(nums, [](int num) { return num >= 0; });
    const long sum = accumulate(nums.begin(), nums.end(), 0L);
    if (allPositives)
      return sum;
    const int maxNum = ranges::max(nums);
    if (maxNum < 0)
      return maxNum;

    long ans = LONG_MIN;
    unordered_map<int, vector<int>> numToIndices;
    SegmentTree tree(nums);

    for (int i = 0; i < nums.size(); ++i)
      numToIndices[nums[i]].push_back(i);

    for (const auto& [num, indices] : numToIndices) {
      for (const int index : indices)
        tree.update(index, 0);
      ans = max(ans, tree.getMaxSubarraySum());
      for (const int index : indices)
        tree.update(index, num);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3410. Maximize Subarray Sum After Removing All Occurrences of One Element LeetCode Solution in Java

class Solution {
 public:
  long long maxSubarraySum(vector<int>& nums) {
    long ans = ranges::max(nums);
    long prefix = 0;
    long minPrefix = 0;
    // the minimum prefix sum that can have a negative number removed
    long modifiedMinPrefix = 0;
    unordered_map<int, int> count;
    // minPrefixPlusRemoval[num] := the minimum prefix sum plus removed `num`
    unordered_map<int, long> minPrefixPlusRemoval;

    for (const int num : nums) {
      prefix += num;
      ans = max(ans, prefix - modifiedMinPrefix);
      if (num < 0) {
        ++count[num];
        minPrefixPlusRemoval[num] =
            min(minPrefixPlusRemoval[num], minPrefix) + num;
        modifiedMinPrefix =
            min({modifiedMinPrefix, count[num] * static_cast<long>(num),
                 minPrefixPlusRemoval[num]});
      }
      minPrefix = min(minPrefix, prefix);
      modifiedMinPrefix = min(modifiedMinPrefix, minPrefix);
    }

    return ans;
  }
};
// code provided by PROGIEZ

3410. Maximize Subarray Sum After Removing All Occurrences of One Element LeetCode Solution in Python

class Solution {
  public long maxSubarraySum(int[] nums) {
    long ans = Arrays.stream(nums).max().getAsInt();
    long prefix = 0;
    long minPrefix = 0;
    // the minimum prefix sum that can have a negative number removed
    long modifiedMinPrefix = 0;
    Map<Integer, Integer> count = new HashMap<>();
    // minPrefixPlusRemoval[num] := the minimum prefix sum plus removed `num`
    Map<Integer, Long> minPrefixPlusRemoval = new HashMap<>();

    for (int num : nums) {
      prefix += num;
      ans = Math.max(ans, prefix - modifiedMinPrefix);
      if (num < 0) {
        count.merge(num, 1, Integer::sum);
        minPrefixPlusRemoval.put(
            num, Math.min(minPrefixPlusRemoval.getOrDefault(num, 0L), minPrefix) + num);
        modifiedMinPrefix = Math.min(modifiedMinPrefix,
                                     Math.min(count.get(num) * num, minPrefixPlusRemoval.get(num)));
      }
      minPrefix = Math.min(minPrefix, prefix);
      modifiedMinPrefix = Math.min(modifiedMinPrefix, minPrefix);
    }

    return ans;
  }
}
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.