3487. Maximum Unique Subarray Sum After Deletion Solution

The problem

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.

Example 1:

Input: nums = [1,2,3,4,5]

Output: 15

Explanation:

Select the entire array without deleting any element to obtain the maximum sum.

Example 2:

Input: nums = [1,1,0,1,1]

Output: 1

Explanation:

Delete the element nums[0] == 1, nums[1] == 1, nums[2] == 0, and nums[3] == 1. Select the entire array [1] to obtain the maximum sum.

Example 3:

Input: nums = [1,2,-1,-2,1,0,-1]

Output: 3

Explanation:

Delete the elements nums[2] == -1 and nums[3] == -2, and select the subarray [2, 1] from [1, 2, 1, 0, -1] to obtain the maximum sum.

Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Approach overview

Problem Overview: You are given an array of integers. You can delete elements so the remaining subarray contains only unique values. The goal is to maximize the sum of that subarray. The challenge is ensuring uniqueness while keeping the sum as large as possible.

Approach 1: Brute Force Enumeration (O(n²) time, O(n) space)

Check every possible subarray and verify whether all elements are unique. For each starting index, expand the subarray while tracking elements in a HashSet. If a duplicate appears, stop expanding that window. Maintain the running sum and update the maximum whenever the subarray remains unique. This approach is straightforward but inefficient because every start index may scan the rest of the array.

Approach 2: Greedy + Hash Table Sliding Window (O(n) time, O(n) space)

Use a sliding window with two pointers and a HashSet to track elements currently inside the window. Iterate the right pointer across the array while adding values to the running sum. If a duplicate appears, move the left pointer forward and remove elements from the set until the duplicate disappears. This effectively simulates deleting elements from the current window to restore uniqueness. Each element enters and leaves the window at most once, giving linear time complexity.

The greedy insight is that a valid window must contain only unique values. When a duplicate appears, shrinking the window from the left is always optimal because it removes the earliest conflicting element while preserving as much of the current sum as possible. The algorithm continuously maintains the best unique-sum window.

This technique is a standard pattern combining Hash Table lookups with the Array sliding window technique. Many interview problems involving distinct elements or maximum window sums rely on the same idea. The greedy decision of removing elements only when duplicates appear keeps the window valid while exploring all candidates efficiently. Similar patterns appear in problems involving Greedy optimization and distinct-element constraints.

Recommended for interviews: The sliding window with a hash table is the expected solution. The brute force version demonstrates the baseline idea of checking uniqueness, but the O(n) window approach shows you understand how to maintain constraints dynamically while scanning the array.

Solution

We first find the maximum value mx in the array. If mx leq 0, then all elements in the array are less than or equal to 0. Since we need to select a non-empty subarray with the maximum element sum, the maximum element sum would be mx.

If mx > 0, then we need to find all distinct positive integers in the array such that their sum is maximized. We can use a hash table s to record all distinct positive integers, and then iterate through the array, adding up all distinct positive integers.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.

Python

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        mx = max(nums)
        if mx <= 0:
            return mx
        ans = 0
        s = set()
        for x in nums:
            if x < 0 or x in s:
                continue
            ans += x
            s.add(x)
        return ans

Java

class Solution {
    public int maxSum(int[] nums) {
        int mx = Arrays.stream(nums).max().getAsInt();
        if (mx <= 0) {
            return mx;
        }
        boolean[] s = new boolean[201];
        int ans = 0;
        for (int x : nums) {
            if (x < 0 || s[x]) {
                continue;
            }
            ans += x;
            s[x] = true;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maxSum(vector<int>& nums) {
        int mx = ranges::max(nums);
        if (mx <= 0) {
            return mx;
        }
        unordered_set<int> s;
        int ans = 0;
        for (int x : nums) {
            if (x < 0 || s.contains(x)) {
                continue;
            }
            ans += x;
            s.insert(x);
        }
        return ans;
    }
};

TypeScript

function maxSum(nums: number[]): number {
    const mx = Math.max(...nums);
    if (mx <= 0) {
        return mx;
    }
    const s = new Set<number>();
    let ans: number = 0;
    for (const x of nums) {
        if (x < 0 || s.has(x)) {
            continue;
        }
        ans += x;
        s.add(x);
    }
    return ans;
}

public class Solution {
    public int MaxSum(int[] nums) {
        int mx = nums.Max();
        if (mx <= 0) {
            return mx;
        }

        HashSet<int> s = new HashSet<int>();
        int ans = 0;

        foreach (int x in nums) {
            if (x < 0 || s.Contains(x)) {
                continue;
            }
            ans += x;
            s.Add(x);
        }

        return ans;
    }
}

func maxSum(nums []int) (ans int) {
	mx := slices.Max(nums)
	if mx <= 0 {
		return mx
	}
	s := make(map[int]bool)
	for _, x := range nums {
		if x < 0 || s[x] {
			continue
		}
		ans += x
		s[x] = true
	}
	return
}

Rust

use std::collections::HashSet;

impl Solution {
    pub fn max_sum(nums: Vec<i32>) -> i32 {
        let mx = *nums.iter().max().unwrap_or(&0);
        if mx <= 0 {
            return mx;
        }

        let mut s = HashSet::new();
        let mut ans = 0;

        for &x in &nums {
            if x < 0 || s.contains(&x) {
                continue;
            }
            ans += x;
            s.insert(x);
        }

        ans
    }
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force with HashSet	O(n²)	O(n)	Useful for understanding the uniqueness constraint and validating smaller inputs
Greedy Sliding Window + Hash Table	O(n)	O(n)	Optimal approach for large arrays and typical interview solution

Frequently asked questions

Is Maximum Unique Subarray Sum After Deletion easy or hard?

Maximum Unique Subarray Sum After Deletion is categorized as an Easy problem. The core idea is recognizing the sliding window pattern with a hash set to maintain unique elements while maximizing the subarray sum.

Maximum Unique Subarray Sum After Deletion Python/Java solution

Most implementations use a hash set plus two pointers. Maintain a running sum and expand the right pointer across the array. When duplicates appear, shrink the window from the left and update the sum. The same logic works across Python, Java, C++, Go, TypeScript, Rust, and C#.

How to solve Maximum Unique Subarray Sum After Deletion in O(n)?

Use two pointers to maintain a sliding window and store current elements in a hash set. Expand the window by moving the right pointer and adding values to the running sum. When a duplicate is found, move the left pointer and remove elements from the set until the duplicate disappears. Track the maximum sum seen during this process.

What is the best approach for Maximum Unique Subarray Sum After Deletion?

The best approach uses a sliding window with a hash table (or hash set). Move a right pointer through the array while maintaining a set of elements in the current window. If a duplicate appears, shift the left pointer and remove elements until the window becomes unique again. This greedy technique runs in O(n) time and O(n) space.

Is Maximum Unique Subarray Sum After Deletion asked at Google/Amazon/Meta?

Problems involving unique subarrays and sliding window techniques frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as maximum unique subarray sum or longest substring without repeating characters test similar hash table and two‑pointer patterns.

What data structure is used in Maximum Unique Subarray Sum After Deletion?

A hash table or hash set is the primary data structure used to track whether an element already exists in the current window. It enables constant‑time lookups and removals, which keeps the sliding window algorithm efficient.

What is the time complexity of Maximum Unique Subarray Sum After Deletion?

The optimal solution runs in O(n) time because each element is added to and removed from the sliding window at most once. Hash set lookups and removals are O(1) on average. Space complexity is O(n) in the worst case when all elements in the window are unique.

Maximum Unique Subarray Sum After Deletion solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Maximum Unique Subarray Sum After Deletion solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems