Solution: Maximum Erasure Value
Tags: algorithms, javascript, java, python
Published: 2021-05-28 08:13:30

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/maximum-erasure-value/discuss/1235716).*

---

#### [Leetcode Problem #1695 (*Medium*): Maximum Erasure Value](https://leetcode.com/problems/maximum-erasure-value/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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)`.

---

#### ***Examples:***
>
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 <= 10^5
 - 1 <= nums[i] <= 10^4

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

Like most problems that ask about a contiguous subarray, this problem naturally calls for a **2-pointer sliding window** approach. There are a few ways we can keep track of the contents of the sliding window, but since the constraint upon **nums[i]** is fairly small, we can use the faster **arraymap** (**nmap**) method, rather than a **hashmap**.

So as we iterate our sliding window through **nums**, we'll move our **right** pointer forward, increasing the counter for the appropriate number in **nmap**. If that bucket in **nmap** goes above **1**, then we know that the newly-added number isn't unique in our sliding window, so we need to increase the **left** pointer until the counter is reduced back to **1**.

We should also, of course, keep track of the sum **total** of the sliding window. At each iteration, once we've confirmed the uniqueness of the contents of the sliding window, we should also update our **best** result so far. Then, once we're done, we can just **return best**.

 - _**Time Complexity: O(N)** where **N** is the length of **nums**_
 - _**Space Complexity: O(10001)** for **nmap** keeping track of numbers from **0** to **10^4**_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var maximumUniqueSubarray = function(nums) {
    let nmap = new Int8Array(10001), total = 0, best = 0
    for (let left = 0, right = 0; right < nums.length; right++) {
        nmap[nums[right]]++, total += nums[right]
        while (nmap[nums[right]] > 1)
            nmap[nums[left]]--, total -= nums[left++]
        best = Math.max(best, total)
    }
    return best
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        nmap, total, best, left = [0] * 10001, 0, 0, 0
        for right in nums:
            nmap[right] += 1
            total += right
            while nmap[right] > 1:
                nmap[nums[left]] -= 1
                total -= nums[left]
                left += 1
            best = max(best, total)
        return best
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        short[] nmap = new short[10001];
        int total = 0, best = 0;
        for (int left = 0, right = 0; right < nums.length; right++) {
            nmap[nums[right]]++;
            total += nums[right];
            while (nmap[nums[right]] > 1) {
                nmap[nums[left]]--;
                total -= nums[left++];
            }
            best = Math.max(best, total);
        }
        return best;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        char nmap[10001]{0};
        int total = 0, best = 0;
        for (int left = 0, right = 0; right < nums.size(); right++) {
            nmap[nums[right]]++, total += nums[right];
            while (nmap[nums[right]] > 1)
                nmap[nums[left]]--, total -= nums[left++];
            best = max(best, total);
        }
        return best;
    }
};
```