3487: Maximum Unique Subarray Sum After Deletion

Problem Statement

You're given an integer array nums. You can delete any number of elements (but not all). After deletion, select a contiguous subarray of the remaining elements where:

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

Return the maximum possible sum of such a subarray.

Key Insight

The problem requires maximizing the sum of a contiguous subarray with unique elements after deletion. The key insights are:

1. Negative numbers reduce the sum - They never increase the maximum sum, so we should delete them
2. Duplicates can't coexist - Only one instance of each number can be included in the subarray
3. Positive distinct values are optimal - The maximum sum comes from including all distinct positive numbers
4. Contiguous arrangement is possible - By deleting non-essential elements, we can make distinct positives contiguous

After deleting negatives and duplicates, we can form a contiguous subarray [10,20,30] with sum 60

Approach 1: Distinct Positives (Optimal)

The most efficient approach leverages the insight that the maximum sum comes from all distinct positive numbers:

Algorithm Steps

1. Create a set to store distinct positive numbers
2. Iterate through the array:
   • Add positive numbers to the set (duplicates automatically handled)
3. Sum all distinct positive numbers
4. If the sum is positive, return it
5. Otherwise, return the maximum element in the array

Why This Works

By deleting all negative numbers and duplicates, we can form a contiguous subarray containing all distinct positive numbers. Since positives increase the sum and duplicates/negatives reduce it, this approach guarantees maximum sum. For arrays with no positives, the best we can do is select the largest element (least negative or zero).

Complexity Analysis

Where n is the length of the array. We traverse the array once and store distinct positives.

class Solution {
public:
    int maxSum(vector<int>& nums) {
        unordered_set<int> distinctPositives;
        int maxElement = INT_MIN;
        
        // Collect distinct positives and track maximum element
        for (int num : nums) {
            // Update max element for negative case handling
            if (num > maxElement) maxElement = num;
            
            // Add positive numbers to set
            if (num > 0) {
                distinctPositives.insert(num);
            }
        }
        
        // Calculate sum of distinct positives
        int total = 0;
        for (int num : distinctPositives) {
            total += num;
        }
        
        // Return sum if positive, else return max element
        return total > 0 ? total : maxElement;
    }
};

import java.util.*;

class Solution {
    public int maxSum(int[] nums) {
        Set<Integer> distinctPositives = new HashSet<>();
        int maxElement = Integer.MIN_VALUE;
        
        // Process each number in the array
        for (int num : nums) {
            // Update maximum element for negative case
            if (num > maxElement) maxElement = num;
            
            // Add positive numbers to set
            if (num > 0) {
                distinctPositives.add(num);
            }
        }
        
        // Calculate sum of distinct positives
        int total = 0;
        for (int num : distinctPositives) {
            total += num;
        }
        
        // Return sum if positive, else max element
        return total > 0 ? total : maxElement;
    }
}

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        distinct_positives = set()
        max_element = float('-inf')
        
        # Process each number in the array
        for num in nums:
            # Update max element for negative case handling
            if num > max_element:
                max_element = num
                
            # Add positive numbers to set
            if num > 0:
                distinct_positives.add(num)
        
        # Calculate sum of distinct positives
        total = sum(distinct_positives)
        
        # Return sum if positive, else max element
        return total if total > 0 else max_element

Approach 2: Brute Force (For Comparison)

While not optimal, this approach helps understand the problem by checking all possible contiguous subarrays in the original array:

Algorithm Steps

1. Initialize max_sum to smallest integer
2. For each starting index i:
   • Create a set to track seen numbers
   • Initialize current sum to 0
   • For each ending index j from i to end:
     • If number at j is already in set, break (not unique)
     • Add number to set and update current sum
     • Update max_sum if current sum is larger
3. Return max_sum

Why This Is Limited

This approach only considers contiguous segments in the original array. It doesn't account for non-contiguous segments that can be made contiguous after deletion. For example, in [10, -1, 20], it would find [10,-1,20] (sum 29) but miss [10,20] (sum 30).

Complexity Analysis

Where n is the length of the array. For each starting index, we scan the rest of the array.

class Solution {
public:
    int maxSum(vector<int>& nums) {
        int max_sum = INT_MIN;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            unordered_set<int> seen;
            int current_sum = 0;
            
            for (int j = i; j < n; j++) {
                // Break if duplicate found
                if (seen.find(nums[j]) != seen.end()) {
                    break;
                }
                
                seen.insert(nums[j]);
                current_sum += nums[j];
                
                // Update max_sum if current_sum is greater
                if (current_sum > max_sum) {
                    max_sum = current_sum;
                }
            }
        }
        
        return max_sum;
    }
};

import java.util.*;

class Solution {
    public int maxSum(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            Set<Integer> seen = new HashSet<>();
            int currentSum = 0;
            
            for (int j = i; j < n; j++) {
                // Break if duplicate found
                if (seen.contains(nums[j])) {
                    break;
                }
                
                seen.add(nums[j]);
                currentSum += nums[j];
                
                // Update maxSum if currentSum is greater
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        
        return maxSum;
    }
}

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        max_sum = float('-inf')
        n = len(nums)
        
        for i in range(n):
            seen = set()
            current_sum = 0
            
            for j in range(i, n):
                # Break if duplicate found
                if nums[j] in seen:
                    break
                    
                seen.add(nums[j])
                current_sum += nums[j]
                
                # Update max_sum if current_sum is greater
                if current_sum > max_sum:
                    max_sum = current_sum
                    
        return max_sum

Edge Cases and Testing

1. All Negative Numbers

Input: [-5, -3, -1, -2]
Output: -1
Explanation: No positives, so return the maximum element (-1)

2. With Zeros

Input: [0, -1, 0, 2, -3]
Output: 2
Explanation: Distinct positives are {2}, sum=2

3. Duplicate Positives

Input: [5, 3, 5, 4, 3]
Output: 12
Explanation: Distinct positives {5,3,4} sum to 12

4. Mixed with Negatives

Input: [10, -5, 8, -3, 6]
Output: 24
Explanation: Distinct positives {10,8,6} sum to 24

5. All Zeros

Input: [0, 0, 0, 0]
Output: 0
Explanation: No positives, maximum element is 0

Frequently Asked Questions