Problem Description

You are given an integer array nums. You can delete any number of elements from the array (but cannot delete all elements - the array must remain non-empty). After deleting elements, you need to select a contiguous subarray from the remaining elements.

The selected subarray must satisfy two conditions:

1. All elements in the subarray must be unique (no duplicates)
2. The sum of elements in the subarray should be as large as possible

Your task is to return the maximum possible sum of such a subarray.

For example, if you have nums = [1, 2, 3, 2, 4], you could:

• Delete nothing and select subarray [1, 2, 3] with sum = 6
• Delete nothing and select subarray [3, 2, 4] with sum = 9
• Delete the second occurrence of 2 to get [1, 2, 3, 4] and select the entire array with sum = 10

The key insight is that you want to maximize the sum while ensuring all elements in your chosen subarray are unique. Since you can delete elements strategically, you can remove duplicates and negative numbers that would decrease your sum, then select the optimal subarray from what remains.

Intuition

Let's think about what we're trying to maximize. We want a subarray with unique elements that has the maximum sum possible.

First observation: Since we can delete any elements we want (except all of them), we have complete control over which elements remain in the array. This is a powerful ability - we can essentially "design" our array to be optimal.

Second observation: For maximizing sum with unique elements, negative numbers are generally bad for us (they decrease the sum), and duplicate positive numbers are also problematic (we can only use one copy due to the uniqueness constraint).

This leads to a key insight: Why would we ever keep negative numbers or duplicates if we can delete them? If we have the freedom to delete elements, the optimal strategy becomes clear:

• Keep all unique positive numbers
• Delete all negative numbers (unless all numbers are negative)
• Delete duplicate occurrences of positive numbers

Wait, but the problem asks for a subarray, not just any subset. Here's the crucial realization: After we delete all unwanted elements (negatives and duplicates), we can arrange the remaining elements however we want. Since all remaining elements are positive and unique, we'd want them all in one contiguous subarray to maximize the sum.

Special case: If all numbers in the original array are negative or zero, we can't delete everything (array must be non-empty). In this case, the best we can do is select a subarray containing just the maximum element (which would be the least negative or zero).

This greedy approach works because we're not constrained by the original order - we can delete and rearrange to create the optimal configuration where all unique positive numbers form a single contiguous subarray.

Learn more about Greedy patterns.

Solution Approach

The implementation follows the greedy strategy we identified:

1. Find the maximum element: First, we find the maximum value mx in the array using mx = max(nums). This helps us handle the special case where all elements are non-positive.

2. Handle the special case: If mx <= 0, it means all elements in the array are negative or zero. Since we must keep at least one element and form a non-empty subarray, the best we can do is return mx (the least negative or zero value).

3. Collect unique positive numbers: If there are positive numbers in the array, we use a hash set s to track which positive numbers we've already seen. We iterate through the array and for each element x:

   • Skip if x < 0 (negative numbers decrease our sum)
   • Skip if x in s (we've already counted this positive number)
   • Otherwise, add x to our running sum ans and mark it as seen by adding to set s

The algorithm works as follows:

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

Time Complexity: O(n) where n is the length of the array. We make one pass to find the maximum and one pass to collect unique positive numbers.

Space Complexity: O(k) where k is the number of unique positive integers in the array. In the worst case, this could be O(n) if all elements are unique and positive.

The beauty of this solution is that it transforms the problem from finding an optimal subarray to simply collecting all unique positive numbers, leveraging the fact that we can delete elements to create the ideal configuration.

Example Walkthrough

Let's walk through the solution with nums = [3, -1, 2, 3, 5, -2, 2].

Step 1: Find the maximum element

• mx = max(nums) = 5
• Since mx > 0, we have positive numbers, so we proceed to collect unique positives.

Step 2: Initialize tracking variables

• ans = 0 (running sum)
• s = set() (to track seen positive numbers)

Step 3: Iterate through the array

Step 4: Return result

• Return ans = 10

This corresponds to deleting -1, -2, and the duplicate occurrences of 3 and 2, leaving us with [3, 2, 5]. We can then select this entire array as our subarray, giving us the maximum sum of 10.

Special case example: If nums = [-4, -2, -5], then mx = -2. Since mx <= 0, we immediately return -2, which represents selecting just the subarray [-2] (the least negative value).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• Finding the maximum element using max(nums) takes O(n) time
• The for loop iterates through all elements in nums once, which takes O(n) time
• The set operations x in s and s.add(x) are O(1) on average
• Overall, the dominant operations are linear scans through the array

The space complexity is O(n), where n is the length of the array nums. This is because:

• The set s can potentially store all unique positive elements from nums
• In the worst case where all elements are unique and positive, the set will contain n elements
• Therefore, the space required grows linearly with the input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Problem Requirements

The Mistake: Many people initially interpret this problem as a traditional "maximum subarray sum with unique elements" problem where you must find a contiguous subarray in the original array without any deletions allowed. They might try to use sliding window or dynamic programming approaches to find the best contiguous subarray with unique elements.

Why It Happens: The problem statement mentions "contiguous subarray" which triggers pattern recognition for classic subarray problems. Readers might miss the crucial detail that you can delete elements first, which fundamentally changes the problem.

The Fix: Recognize that the ability to delete elements means you can rearrange the array to your advantage. Once you can delete any elements you want (except all of them), you can remove all duplicates and negative numbers, then arrange the remaining unique positive numbers contiguously. This transforms the problem into simply summing all unique positive values.

Pitfall 2: Forgetting Edge Cases with Non-Positive Numbers

The Mistake: Implementing only the logic to sum unique positive numbers without handling the case where all numbers in the array are negative or zero:

def maxSum(self, nums: List[int]) -> int:
    total_sum = 0
    seen = set()
    for num in nums:
        if num > 0 and num not in seen:
            total_sum += num
            seen.add(num)
    return total_sum  # Returns 0 when all numbers are negative!

Why It Happens: When focusing on maximizing the sum, it's natural to think "just take all positive unique numbers." However, the problem requires the array to remain non-empty, so when all numbers are non-positive, returning 0 violates this constraint.

The Fix: Always check if the maximum value in the array is non-positive. If it is, return that maximum value (the least negative number) since you must keep at least one element:

max_value = max(nums)
if max_value <= 0:
    return max_value

Pitfall 3: Overthinking the Subarray Selection

The Mistake: After collecting unique positive numbers, trying to find the "optimal contiguous subarray" among them, perhaps using Kadane's algorithm or similar approaches.

Why It Happens: The phrase "contiguous subarray" in the problem statement makes it seem like you need to carefully select which portion of your processed array to use.

The Fix: Once you've deleted all unwanted elements (negatives and duplicates), you can arrange the remaining unique positive numbers however you want. The optimal strategy is always to include all of them in your subarray since they're all positive and contribute to the sum. The "contiguous" requirement becomes trivial when you control the arrangement.