Maximum unique subarray sum after deletion

Array Hash Table Greedy

40.5% acceptance

Feb 25, 2026

473

You are given an integer array nums. You are allowed to delete any number of elements from nums without making it empty. After performing the deletions, select a subarray of nums such that: All elements in the subarray are unique. The sum of the elements in the subarray is maximized. Return the maximum sum of such a subarray.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum(nums: Vec<i32>) -> i32 {
    // After deletions, remaining array is a subsequence. 
    // We select a contiguous subarray of the remaining (which is the original with some deleted).
    // A contiguous subarray of a subsequence = a subsequence of the original.
    // So: select a subsequence of nums such that all elements are unique and sum is maximized.
    // Greedy: for each distinct value, keep only if positive. Skip negatives and duplicates.
    // Actually: keep one copy of each positive value.
    let mut seen = std::collections::HashSet::new();
    let mut sum = 0i32;
    for &x in &nums {
      if x > 0 && seen.insert(x) { sum += x; }
    }
    // But also: we need to handle the case where all values are negative.
    // Must select at least 1 element (non-empty array → non-empty subarray).
    // Actually problem says "not making it empty" for deletions, then select a subarray.
    // If sum=0 (all non-positive unique values), we need to pick the max single element.
    if sum == 0 {
      *nums.iter().max().unwrap_or(&0)
    } else {
      sum
    }
  }
}