Maximum Unique Subarray Sum After Deletion

Difficulty: Easy | Acceptance: 40.50% | Paid: No Topics: Array, Hash Table, Greedy

You are given an array of integers. You can delete at most one element from the array. After the deletion (if any), find the maximum sum of a subarray where all elements are unique.

Return the maximum possible sum.

Examples

Example 1

Input: nums = [4,2,4,5,6]
Output: 17
Explanation: Delete the first 4, then the subarray [2,4,5,6] has all unique elements with sum 17.

Example 2

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The subarray [5,2,1] has all unique elements with sum 8. No deletion needed.

Example 3

Input: nums = [1,2,3,2,1]
Output: 6
Explanation: Delete the first 2, then the subarray [1,3,2,1] has all unique elements with sum 7.

Constraints

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

• Brute Force
• Sliding Window with Hash Set
• Sliding Window with Deletion Tracking

Examples

Example 1

Input: nums = [4,2,4,5,6]
Output: 17
Explanation: Delete the first 4, then the subarray [2,4,5,6] has all unique elements with sum 17.

Example 2

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The subarray [5,2,1] has all unique elements with sum 8. No deletion needed.

Example 3

Input: nums = [1,2,3,2,1]
Output: 7
Explanation: Delete the first 2, then the subarray [1,3,2,1] has all unique elements with sum 7.

Constraints

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Brute Force

Intuition Try deleting each element (or none) and find the maximum sum of a subarray with unique elements for each case.

Steps

• Iterate through each index, considering deleting that element (or no deletion)
• For each modified array, use a sliding window to find the maximum sum of a subarray with unique elements
• Track and return the maximum sum across all cases

class Solution:
    def maxUniqueSubarraySum(self, nums):
        n = len(nums)
        max_sum = float('-inf')
        
        # Try deleting each element (or none)
        for delete_idx in range(-1, n):
            seen = set()
            current_sum = 0
            window_sum = 0
            
            for i in range(n):
                if i == delete_idx:
                    continue
                
                if nums[i] in seen:
                    # Reset window
                    seen.clear()
                    window_sum = 0
                
                seen.add(nums[i])
                window_sum += nums[i]
                current_sum = max(current_sum, window_sum)
            
            max_sum = max(max_sum, current_sum)
        
        return max_sum

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: Simple but inefficient for large inputs

Sliding Window with Hash Set

Intuition Use a sliding window with a hash set to track unique elements. When a duplicate is found, shrink the window from the left.

Steps

• Maintain a sliding window with a hash set of unique elements
• Track the current window sum
• When encountering a duplicate, shrink the window until the duplicate is removed
• Update the maximum sum at each step

class Solution:
    def maxUniqueSubarraySum(self, nums):
        seen = set()
        left = 0
        max_sum = float('-inf')
        current_sum = 0
        
        for right in range(len(nums)):
            while nums[right] in seen:
                seen.remove(nums[left])
                current_sum -= nums[left]
                left += 1
            
            seen.add(nums[right])
            current_sum += nums[right]
            max_sum = max(max_sum, current_sum)
        
        return max_sum

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Efficient but doesn’t account for the deletion option

Sliding Window with Deletion Tracking

Intuition Extend the sliding window approach to handle one deletion. Track if we’ve used our deletion and handle duplicates accordingly.

Steps

• Use a hash map to track the count of each element in the window
• Maintain a flag for whether we’ve used our deletion
• When encountering a duplicate:
  • If deletion not used, skip the duplicate element
  • If deletion used, shrink window from the left
• Track and update the maximum sum

class Solution:
    def maxUniqueSubarraySum(self, nums):
        from collections import defaultdict
        
        count = defaultdict(int)
        left = 0
        max_sum = float('-inf')
        current_sum = 0
        deleted = False
        
        for right in range(len(nums)):
            if count[nums[right]] > 0:
                if not deleted:
                    deleted = True
                else:
                    while count[nums[right]] > 0:
                        count[nums[left]] -= 1
                        current_sum -= nums[left]
                        left += 1
            
            count[nums[right]] += 1
            current_sum += nums[right]
            max_sum = max(max_sum, current_sum)
        
        return max_sum

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Optimal solution that handles the deletion option efficiently