Maximum Erasure Value - Leetcode Solution

Problem Statement:

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].

Approach:

The problem requires us to find the maximum sum of elements of a subarray containing unique elements. The brute-force approach to solve this problem is to try all possible subarrays that contain unique elements and calculate the sum of each subarray. The maximum sum of all subarrays can be determined as the answer. But this approach takes O(N^3) time and is impractical for large inputs.

A slightly more efficient approach is to use a hash table to store the last index of each element encountered. We can then maintain two pointers i and j such that i points to the starting index of the subarray and j points to the end index. Initially, both i and j are equal to 0.

As we traverse the array and encounter a new element, we check its index in the hash table. If it is greater than or equal to i, it means that the element is already present in the subarray and we need to update i to the next index of the duplicate element. We then calculate the sum of the current subarray and update the maximum sum so far.

At each step, we update the hash table with the current index of the element. When we encounter an element that is not already present in the subarray, we update j and continue traversing the array. The time complexity of this approach is O(N) as we only traverse the array once.

Solution:

The solution to the Maximum Erasure Value problem on Leetcode is as follows:

class Solution { public: int maximumUniqueSubarray(vector<int>& nums) { unordered_map<int, int> mp; int i = 0, j = 0, n = nums.size(); int sum = 0, max_sum = 0;

    while (j < n) {
        if (mp.find(nums[j]) != mp.end() && mp[nums[j]] >= i) {
            sum -= nums[i];
            i = mp[nums[j]] + 1;
        }
        sum += nums[j];
        mp[nums[j]] = j;
        j++;
        max_sum = max(max_sum, sum);
    }
    
    return max_sum;
}

};

In this solution, we first declare an unordered_map mp to store the last index of each element encountered in the array.

We then declare two pointers i and j to keep track of the subarray and initialize them to 0. We also initialize the variables sum and max_sum to 0.

Next, we traverse the array using the pointer j.

At each step, we check if the current element nums[j] is already present in the subarray mp and its last index is greater than or equal to i. If it is, we update the sum by subtracting nums[i] from it and update i to the next index of the duplicate element.

If the current element is not already present in the subarray, we update the sum by adding nums[j] to it and update mp with the current index of the element.

We then update j and calculate the maximum sum so far using the max function.

Finally, we return the maximum sum as the answer.

Time Complexity:

The time complexity of this solution is O(N) as we only traverse the array once.

Therefore, this solution is an optimal solution to the Maximum Erasure Value problem on Leetcode.

1