Maximize subarray sum after removing all occurrences of one element

Array Dynamic Programming Segment Tree

22.9% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn max_subarray_sum(nums: Vec<i32>) -> i64 {
    let mut pre: HashMap<i64, i64> = HashMap::new();

    let mut res = nums[0] as i64;
    let mut prefix = 0i64;
    let mut low = 0i64;
    pre.insert(0, 0);

    for &n in &nums {
      let n64 = n as i64;
      prefix += n64;
      res = res.max(prefix - low);

      if n < 0 {
        let pre0 = pre[&0];
        let val = pre.get(&n64).copied().unwrap_or(pre0).min(pre0) + n64;
        pre.insert(n64, val);
        low = low.min(val);
      }

      let pre0_new = pre[&0].min(prefix);
      pre.insert(0, pre0_new);
      low = low.min(pre0_new);
    }

    res
  }
}