Solution: Maximum Erasure Value

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #1695 (Medium): Maximum Erasure Value

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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;    }};