Maximum Unique Subarray Sum After Deletion - Solution & Explanation
Problem Statement
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.
Detailed 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 |
Video Solution
Maximum Unique Subarray Sum After Deletion | Constant Space | Leetcode 3487 | codestorywithMIK • codestorywithMIK • 6,488 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Unique Subarray Sum After Deletion easy or hard?
Maximum Unique Subarray Sum After Deletion Python/Java solution
How to solve Maximum Unique Subarray Sum After Deletion in O(n)?
What is the best approach for Maximum Unique Subarray Sum After Deletion?
Is Maximum Unique Subarray Sum After Deletion asked at Google/Amazon/Meta?
What data structure is used in Maximum Unique Subarray Sum After Deletion?
What is the time complexity of Maximum Unique Subarray Sum After Deletion?
Ready to solve this problem?
Practice Maximum Unique Subarray Sum After Deletion with our built-in code editor and test cases.
Practice on FleetCode