# Maximum Unique Subarray Sum After Deletion
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-unique-subarray-sum-after-deletion)
Canonical: https://scaleengineer.com/dsa/problems/maximum-unique-subarray-sum-after-deletion
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table
---
## Problem
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.

**Example 1:**

**Input:** nums = \[1,2,3,4,5\]

**Output:** 15

**Explanation:**

Select the entire array without deleting any element to obtain the maximum sum.

**Example 2:**

**Input:** nums = \[1,1,0,1,1\]

**Output:** 1

**Explanation:**

Delete the element `nums[0] == 1`, `nums[1] == 1`, `nums[2] == 0`, and `nums[3] == 1`. Select the entire array `[1]` to obtain the maximum sum.

**Example 3:**

**Input:** nums = \[1,2,-1,-2,1,0,-1\]

**Output:** 3

**Explanation:**

Delete the elements `nums[2] == -1` and `nums[3] == -2`, and select the subarray `[2, 1]` from `[1, 2, 1, 0, -1]` to obtain the maximum sum.

**Constraints:**

* `1 <= nums.length <= 100`
* `-100 <= nums[i] <= 100`

# Approaches
## Brute-Force Enumeration
This approach directly translates the problem statement into a computational procedure. It exhaustively explores every possibility by first generating all non-empty subsequences that can be formed by deleting zero or more elements from the original array. For each of these subsequences, it then examines all of its contiguous subarrays. Finally, for each subarray, it checks for the uniqueness of its elements and calculates its sum, keeping track of the maximum sum found across all valid subarrays.
**Time:** O(2^N * N^3). There are 2^N subsequences. For a subsequence of length k, there are O(k^2) subarrays. Checking uniqueness and summing takes O(k). Since k can be up to N, the complexity is dominated by the exponential generation of subsequences and the polynomial work done on each. · **Space:** O(N), where N is the length of the input array. This space is used for the recursion stack and to store the `currentSubsequence`.
**Pros:** It is guaranteed to find the correct answer because it explores the entire search space defined by the problem.; The logic is a direct, albeit naive, implementation of the problem description.
**Cons:** Extremely inefficient due to its exponential time complexity, making it impractical for the given constraints (n <= 100).; The implementation is complex due to multiple levels of recursion and iteration.
### Explanation
The core of this method is a recursive backtracking algorithm to generate all 2^n - 1 non-empty subsequences. For each subsequence generated, we must then find its maximum sum unique subarray. The most straightforward way to do this is to generate all of its O(k^2) subarrays (where k is the subsequence length), and for each one, check for uniqueness and calculate the sum in O(k) time. This leads to a very high time complexity.

Here is a conceptual code structure:
```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    long maxSum = Long.MIN_VALUE;

    public int maximumUniqueSubarraySumAfterDeletion(int[] nums) {
        generateSubsequences(nums, 0, new ArrayList<>());
        return (int) maxSum;
    }

    private void generateSubsequences(int[] nums, int index, List<Integer> currentSubsequence) {
        if (index == nums.length) {
            if (!currentSubsequence.isEmpty()) {
                processSubsequence(currentSubsequence);
            }
            return;
        }

        // Exclude nums[index]
        generateSubsequences(nums, index + 1, currentSubsequence);

        // Include nums[index]
        currentSubsequence.add(nums[index]);
        generateSubsequences(nums, index + 1, currentSubsequence);
        currentSubsequence.remove(currentSubsequence.size() - 1);
    }

    private void processSubsequence(List<Integer> sub) {
        for (int i = 0; i < sub.size(); i++) {
            for (int j = i; j < sub.size(); j++) {
                // Extract subarray from sub[i...j]
                List<Integer> subarray = sub.subList(i, j + 1);
                Set<Integer> uniqueElements = new HashSet<>(subarray);
                
                if (uniqueElements.size() == subarray.size()) {
                    // It's a unique subarray
                    long currentSum = 0;
                    for (int num : subarray) {
                        currentSum += num;
                    }
                    maxSum = Math.max(maxSum, currentSum);
                }
            }
        }
    }
}
```
### Algorithm
- Initialize a global variable `max_sum` to a very small value.
- Implement a recursive helper function, say `generateSubsequences(index, currentSubsequence)`, to generate all subsequences.
- The function explores two branches at each `index`: one including `nums[index]` in `currentSubsequence` and one not including it.
- The base case for the recursion is when `index` reaches the end of the array `nums`.
- Whenever a non-empty subsequence is formed, iterate through all of its contiguous subarrays using nested loops (for start and end pointers).
- For each subarray, use a `HashSet` to verify if all its elements are unique.
- If the subarray is unique, calculate its sum and update `max_sum = max(max_sum, current_sum)`.
- After the recursion completes, `max_sum` will hold the result.

## Sliding Window on All Subsequences
This approach improves upon the naive brute-force method. While we still generate all possible non-empty subsequences, we optimize the process of analyzing each one. Instead of checking every single subarray of a subsequence (which takes O(k^3) time), we use an efficient sliding window algorithm. This algorithm can find the maximum sum unique subarray for a given subsequence of length k in just O(k) time. This significantly speeds up the processing for each subsequence, though the overall complexity remains exponential.
**Time:** O(2^N * N). We generate 2^N subsequences, and for each subsequence of length k, the sliding window takes O(k) time. The sum of lengths of all subsequences is N * 2^(N-1), leading to this complexity. · **Space:** O(N). The space is required for the recursion stack, storing the current subsequence, and the `HashSet` used in the sliding window.
**Pros:** Significantly more efficient than the naive brute-force approach for the subproblem of analyzing a single subsequence.; It correctly solves the problem by exploring all possibilities.
**Cons:** The time complexity is still exponential due to the generation of all subsequences.; It is not a feasible solution for the given constraints of N up to 100.
### Explanation
The main improvement here is the `processSubsequence` function. By using a sliding window, we avoid the nested loops for generating subarrays. The sliding window efficiently finds the longest unique subarray starting at each possible position.

```java
// Helper function to be called for each subsequence
private long findMaxUniqueSubarraySum(List<Integer> sub) {
    if (sub.isEmpty()) {
        return Long.MIN_VALUE;
    }
    long subMaxSum = Long.MIN_VALUE;
    long currentSum = 0;
    int left = 0;
    Set<Integer> windowElements = new HashSet<>();

    for (int right = 0; right < sub.size(); right++) {
        int num = sub.get(right);
        while (windowElements.contains(num)) {
            int leftNum = sub.get(left);
            windowElements.remove(leftNum);
            currentSum -= leftNum;
            left++;
        }
        windowElements.add(num);
        currentSum += num;
        subMaxSum = Math.max(subMaxSum, currentSum);
    }
    return subMaxSum;
}

// The main logic would still generate all subsequences and call this helper.
// maxSum = Math.max(maxSum, findMaxUniqueSubarraySum(currentSubsequence));
```
This reduces the work for a subsequence of length k from O(k^3) to O(k), leading to a better overall time complexity, but it's still limited by the O(2^N) subsequences.
### Algorithm
- Initialize a global variable `max_sum` to a very small value.
- Generate all 2^N - 1 non-empty subsequences of `nums` using recursion, similar to the first approach.
- For each generated subsequence `sub`:
  - Apply a sliding window algorithm to find the maximum sum of a unique subarray within `sub`.
  - The sliding window function would use two pointers, `left` and `right`, a `HashSet` to track elements in the window, and a `current_sum`.
  - It iterates `right` across the subsequence, expanding the window. If a duplicate is found, it shrinks the window from the `left` until it's unique again.
  - The maximum `current_sum` seen during this scan is the result for `sub`.
- Update the global `max_sum` with the result from each subsequence.
- Return the final `max_sum`.

## Greedy Sum of Unique Positive Numbers
This optimal approach stems from a crucial insight: the ability to delete any number of elements allows us to form a subsequence containing any set of elements from the original array, as long as their relative order is preserved. The problem then simplifies to finding a subsequence with unique elements that has the maximum possible sum.

To maximize the sum, we should greedily include all unique positive numbers. Including any negative number would decrease the sum. Therefore, the best possible unique subarray we can form is one consisting of all unique positive numbers. If there are no unique positive numbers, we must pick the best single element, which would be the maximum element in the array.
**Time:** O(N), where N is the length of the input array. We perform a single pass to populate the set and find the max element, and another pass over the unique elements (at most N elements). · **Space:** O(K), where K is the number of unique elements in `nums`. In the worst case, K can be equal to N, so the space complexity is O(N). This space is used for the `HashSet`.
**Pros:** Extremely efficient, with a linear time complexity.; Simple and straightforward to implement once the core logic is understood.; Correctly handles all edge cases, such as arrays with all negative numbers.
**Cons:** The reasoning behind this approach is not immediately obvious from the problem's phrasing, which can be misleading.
### Explanation
The problem's complexity is hidden in its phrasing. The freedom of deletion is the key. Let's say the unique positive numbers in `nums` are `p1, p2, ..., pk`. We can always form a subsequence by picking one instance of each of these numbers in the order they appear in `nums`. This subsequence, let's call it `S`, consists of unique positive numbers. `S` is itself a subarray of `S`, and it's unique. Its sum is the sum of all unique positive numbers. Any other combination would result in a smaller or equal sum.

If there are no unique positive numbers, the sum of any unique subsequence will be less than or equal to 0. To get the maximum possible sum, which must be non-empty, we should pick the largest number available, which is simply the maximum value in the original `nums` array.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maximumUniqueSubarraySumAfterDeletion(int[] nums) {
        Set<Integer> uniqueNums = new HashSet<>();
        int maxElement = Integer.MIN_VALUE;
        for (int num : nums) {
            uniqueNums.add(num);
            if (num > maxElement) {
                maxElement = num;
            }
        }

        long positiveSum = 0;
        boolean hasPositive = false;
        for (int num : uniqueNums) {
            if (num > 0) {
                positiveSum += num;
                hasPositive = true;
            }
        }

        if (hasPositive) {
            return (int) positiveSum;
        } else {
            // If no unique positive numbers, the best we can do is pick the largest number.
            // This handles cases with all negatives, or only 0s and negatives.
            return maxElement;
        }
    }
}
```
### Algorithm
- Create a `HashSet` to find all the unique numbers in the input array `nums`.
- Initialize a variable `positiveSum` to 0.
- Iterate through the unique numbers in the `HashSet`. For each number, if it is positive, add it to `positiveSum`.
- After checking all unique numbers, if `positiveSum` is greater than 0, it means we can form a unique subarray with a positive sum. This sum is the maximum possible, so return `positiveSum`.
- If `positiveSum` is 0, it implies there are no unique positive numbers (all unique numbers are zero or negative). Since the problem requires a non-empty result, we must select at least one element. To maximize the sum, we should pick the single largest element from the original `nums` array. Find this maximum value and return it.

# Solutions
### Java

```java
class Solution {
public
  int maxSum(int[] nums) {
    int mx = Arrays.stream(nums).max().getAsInt();
    if (mx <= 0) {
      return mx;
    }
    boolean[] s = new boolean[201];
    int ans = 0;
    for (int x : nums) {
      if (x < 0 || s[x]) {
        continue;
      }
      ans += x;
      s[x] = true;
    }
    return ans;
  }
}

```

### Python

```python
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

```

### CPP

```cpp
class Solution {
public:
  int maxSum(vector<int> &nums) {
    int mx = ranges ::max(nums);
    if (mx <= 0) {
      return mx;
    }
    unordered_set<int> s;
    int ans = 0;
    for (int x : nums) {
      if (x < 0 || s.contains(x)) {
        continue;
      }
      ans += x;
      s.insert(x);
    }
    return ans;
  }
};

```