Maximum Unique Subarray Sum After Deletion

Problem Description

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:

1. All elements in the subarray are unique.
2. The sum of the elements in the subarray is maximized.

Return the maximum sum of such a subarray.

Key Insights

• A subarray must consist of unique elements.
• The sum of the selected subarray should be maximized.
• We can utilize a sliding window approach to maintain a window of unique elements and track the maximum sum efficiently.
• We need to handle negative values carefully since they can lower the overall sum.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(min(n, m)), where n is the length of nums and m is the range of the input values (in this case, from -100 to 100).

Solution

To solve the problem, we can use the sliding window technique combined with a hash set to keep track of unique elements. The algorithm works as follows:

1. Initialize a variable to store the maximum sum and set the current sum to 0.
2. Use two pointers to represent the start and end of the sliding window.
3. Expand the window by moving the end pointer, adding the numbers to the current sum.
4. If a duplicate is encountered, shrink the window from the start until all elements are unique again.
5. Continuously update the maximum sum found during the process.

Code Solutions