Maximum Unique Subarray Sum After Deletion

Problem Description

Given an integer array nums, you are allowed to delete any number of elements (without making the array empty). After deletions, you select a contiguous subarray (from the resulting array) in which every element is unique. The goal is to maximize the sum of the elements in the chosen subarray. Return the maximum sum possible.

Key Insights

• Deletions are arbitrary, so you can remove any duplicates to achieve a unique set of numbers.
• Since order is preserved after deletion, any subsequence (picked from the original array) can be made contiguous.
• You only need to include each unique number at most once.
• For positive numbers, adding them increases the sum, so include every distinct positive value.
• Negative numbers and zeros do not help the sum (unless there is no positive number); in that case, the best you can do is choose the maximum number from nums.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The insight is that because deletions are free, the optimal strategy is to construct a subsequence containing each unique number at most once. Since including a positive number increases the sum, you want to include every unique positive number. For non-positive numbers, they would only decrease the total sum when combined with positive numbers. However, if the array contains no positive values, you must choose the maximum (i.e. least negative or zero) element to satisfy the non-empty condition.

The algorithm:

1. Iterate through nums and add each number greater than 0 to a set to ensure uniqueness.
2. If the set is non-empty, return the sum of these unique positive numbers.
3. If no positive number exists, return the maximum element from nums.

This approach uses a set for constant-time look-ups and runs in linear time relative to the length of the array.

Code Solutions