# Maximum Erasure Value
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-erasure-value)
Canonical: https://scaleengineer.com/dsa/problems/maximum-erasure-value
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table
**Companies:** [Cashfree](https://scaleengineer.com/companies/cashfree)
---
## Problem
You are given an array of positive integers `nums` and want to erase a subarray containing **unique elements**. The **score** you get by erasing the subarray is equal to the **sum** of its elements.

Return _the **maximum score** you can get by erasing **exactly one** subarray._

An array `b` is called to be a subarray of `a` if it forms a contiguous subsequence of `a`, that is, if it is equal to `a[l],a[l+1],...,a[r]` for some `(l,r)`.

**Example 1:**

**Input:** nums = [4,2,4,5,6]
**Output:** 17
**Explanation:** The optimal subarray here is [2,4,5,6].

**Example 2:**

**Input:** nums = [5,2,1,2,5,2,1,2,5]
**Output:** 8
**Explanation:** The optimal subarray here is [5,2,1] or [1,2,5].

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 104`

# Approaches
## Brute Force by Checking All Subarrays
This is the most straightforward but naive approach. The idea is to generate every possible contiguous subarray of the input array `nums`. For each of these subarrays, we first check if it contains only unique elements. If it does, we then calculate its sum and update the maximum score found so far if the current sum is greater.
**Time:** O(n^3). There are O(n^2) subarrays, and for each subarray, we iterate through its elements to check for uniqueness and calculate the sum, which takes up to O(n) time. · **Space:** O(n), as the `HashSet` can store up to `n` elements for a subarray of length `n`.
**Pros:** Simple to understand and conceptualize.
**Cons:** Extremely inefficient due to three nested loops.; Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
### Explanation
We can implement this using three nested loops. The outer two loops, with indices `i` and `j`, define the start and end of a subarray. The third loop, with index `k`, iterates through this subarray `nums[i...j]`. Inside this innermost loop, we use a `HashSet` to keep track of the elements we've seen in the current subarray. If we encounter an element that's already in the set, we know the subarray is not unique. If the loop completes without finding duplicates, we calculate the sum and update our global maximum score. This process is repeated for all O(n^2) possible subarrays.

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

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int maxScore = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                Set<Integer> uniqueElements = new HashSet<>();
                int currentSum = 0;
                boolean isUnique = true;
                // Check for uniqueness and calculate sum for subarray nums[i...j]
                for (int k = i; k <= j; k++) {
                    if (!uniqueElements.add(nums[k])) {
                        isUnique = false;
                        break;
                    }
                    currentSum += nums[k];
                }
                
                if (isUnique) {
                    maxScore = Math.max(maxScore, currentSum);
                }
            }
        }
        return maxScore;
    }
}
```
### Algorithm
- Initialize `maxScore` to 0.
- Use a nested loop to generate all possible start `i` and end `j` indices of a subarray.
- For each subarray `nums[i...j]`, create a third loop from `k = i` to `j`.
- Inside the third loop, use a `HashSet` to check for uniqueness. If a duplicate is found, the subarray is invalid.
- If the subarray is unique after checking all its elements, calculate its sum.
- Update `maxScore = max(maxScore, currentSum)`.
- After all subarrays are checked, return `maxScore`.

## Optimized Brute Force
This approach improves upon the pure brute-force method by being slightly more intelligent. Instead of re-generating and re-validating each subarray from scratch, we can fix the starting point of a subarray and extend it to the right one element at a time. We maintain a running sum and check for uniqueness as we expand.
**Time:** O(n^2). The two nested loops lead to a quadratic time complexity. The operations inside the inner loop (HashSet add/contains) take O(1) on average. · **Space:** O(n). The `HashSet` can store up to `n` elements in the worst-case scenario where all elements in the array are unique.
**Pros:** More efficient than the O(n^3) brute-force approach.; Reduces redundant computations by building subarrays incrementally.
**Cons:** This approach is still too slow for large inputs as specified by the problem constraints (n <= 10^5) and will likely time out.
### Explanation
We use two nested loops. The outer loop fixes the starting index `i` of a potential subarray. For each `i`, the inner loop extends the subarray by moving an ending index `j` from `i` to the end of the array. We use a `HashSet` to keep track of the elements in the current subarray `nums[i...j]` and a variable to maintain its sum. As we increment `j`, we check if `nums[j]` would be a duplicate. If it is, we know that any further subarray starting at `i` will also contain this duplicate, so we can stop and move to the next starting position `i+1`. If `nums[j]` is unique, we add it to our set and sum, and update the maximum score.

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

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int maxScore = 0;
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> seen = new HashSet<>();
            int currentSum = 0;
            for (int j = i; j < nums.length; j++) {
                if (seen.contains(nums[j])) {
                    // Subarray from i is no longer unique, break and try from i+1
                    break; 
                }
                seen.add(nums[j]);
                currentSum += nums[j];
                maxScore = Math.max(maxScore, currentSum);
            }
        }
        return maxScore;
    }
}
```
### Algorithm
- Initialize `maxScore` to 0.
- Loop `i` from `0` to `n-1` (this will be the starting index of our subarrays).
- Inside this loop, initialize an empty `HashSet` called `seen` and a `currentSum` to 0.
- Start a second loop with `j` from `i` to `n-1`.
- In the inner loop, check if `nums[j]` is already in `seen`.
  - If it is, this means the subarray `nums[i...j]` contains a duplicate. We break the inner loop and move to the next starting index `i+1`.
  - If it's not, we add `nums[j]` to `seen`, add its value to `currentSum`, and update `maxScore = max(maxScore, currentSum)`.
- Return `maxScore` after the loops complete.

## Sliding Window
The most efficient solution uses the sliding window pattern. This technique is ideal for problems involving contiguous subarrays. We maintain a 'window' (a subarray) that is always guaranteed to have unique elements. We try to expand this window to the right as much as possible. When we encounter a duplicate element, we shrink the window from the left until it becomes valid again. Throughout this process, we keep track of the sum of the current window's elements and update the maximum score.
**Time:** O(n). Both the `right` and `left` pointers traverse the array at most once, and each element is added to and removed from the `HashSet` at most once. All set operations take O(1) on average. · **Space:** O(k), where `k` is the number of unique values in the input array. Given the constraint `1 <= nums[i] <= 10^4`, the space is at most O(10001). In the general case, it's O(min(n, k)).
**Pros:** Optimal time complexity of O(n), making it very efficient for large inputs.; Efficient use of space.
**Cons:** Can be slightly more complex to implement correctly compared to brute-force methods.
### Explanation
We use two pointers, `left` and `right`, to define the boundaries of our sliding window. A `HashSet` is used to efficiently check for the existence of an element in the current window. We iterate through the array with the `right` pointer to expand the window. If `nums[right]` is already in our set, it means we have a duplicate. To fix this, we shrink the window from the left by incrementing the `left` pointer and removing `nums[left]` from the set and the running sum. We repeat this until the element at `nums[right]` is no longer a duplicate in the window `nums[left...right-1]`. After ensuring uniqueness, we add `nums[right]` to the window (and the set/sum). At each step after expansion, the window is valid, so we update our maximum score. Since each element is visited by the `left` and `right` pointers at most once, the overall time complexity is linear.

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

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int n = nums.length;
        Set<Integer> windowElements = new HashSet<>();
        int maxScore = 0;
        int currentSum = 0;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            // Shrink the window from the left if the new element is already present
            while (windowElements.contains(nums[right])) {
                currentSum -= nums[left];
                windowElements.remove(nums[left]);
                left++;
            }
            
            // Expand the window from the right
            currentSum += nums[right];
            windowElements.add(nums[right]);
            
            // Update the maximum score with the sum of the current unique subarray
            maxScore = Math.max(maxScore, currentSum);
        }
        
        return maxScore;
    }
}
```
### Algorithm
- Initialize two pointers, `left = 0` and `right = 0`.
- Initialize `maxScore = 0`, `currentSum = 0`.
- Use a `HashSet` named `windowElements` to store elements in the current window `nums[left...right]`.
- Iterate with the `right` pointer from `0` to `n-1`.
- Inside the loop, check if `nums[right]` is already in `windowElements`.
  - If it is, it's a duplicate. Shrink the window from the left: repeatedly subtract `nums[left]` from `currentSum`, remove `nums[left]` from `windowElements`, and increment `left`, until `nums[right]` is no longer in the set.
- Now that the window is valid, expand it: add `nums[right]` to `currentSum` and `windowElements`.
- The current window `nums[left...right]` is unique. Update `maxScore = max(maxScore, currentSum)`.
- After the loop, return `maxScore`.

# Solutions
### Python

```python
class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int: d = defaultdict(int) s = list(accumulate(nums, initial=0)) ans = j = 0 for i, v in enumerate(nums, 1): j = max(j, d[v]) ans = max(ans, s[i] - s[j]) d[v] = i return ans

```

### Java

```java
class Solution {
public
  int maximumUniqueSubarray(int[] nums) {
    int[] d = new int[10001];
    int n = nums.length;
    int[] s = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = 0, j = 0;
    for (int i = 1; i <= n; ++i) {
      int v = nums[i - 1];
      j = Math.max(j, d[v]);
      ans = Math.max(ans, s[i] - s[j]);
      d[v] = i;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumUniqueSubarray(vector<int> &nums) {
    int d[10001]{};
    int n = nums.size();
    int s[n + 1];
    s[0] = 0;
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = 0, j = 0;
    for (int i = 1; i <= n; ++i) {
      int v = nums[i - 1];
      j = max(j, d[v]);
      ans = max(ans, s[i] - s[j]);
      d[v] = i;
    }
    return ans;
  }
};

```