We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Erasure Value

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires finding a contiguous subarray with unique elements.
  • The score is based on the sum of the elements in the selected subarray.
  • A sliding window approach can be used to maintain a dynamic range of unique elements.
  • Hashing can help keep track of the elements and their frequencies to ensure uniqueness.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a sliding window technique combined with a hash map (or dictionary) to track the elements we have seen and their frequencies. The idea is to maintain two pointers that represent the current window of unique elements. We will expand the right pointer to include new elements and contract the left pointer when we encounter a duplicate. The sum of the current window will be calculated, and we will keep track of the maximum sum encountered.

Code Solutions

def maximumErasureValue(nums):
    left = 0
    current_sum = 0
    max_sum = 0
    num_map = {}
    
    for right in range(len(nums)):
        if nums[right] in num_map:
            # Move the left pointer to the right of the last occurrence of nums[right]
            while nums[right] in num_map:
                current_sum -= nums[left]
                num_map[nums[left]] -= 1
                if num_map[nums[left]] == 0:
                    del num_map[nums[left]]
                left += 1
        
        # Add the current number to the window
        num_map[nums[right]] = num_map.get(nums[right], 0) + 1
        current_sum += nums[right]
        
        # Update the maximum sum
        max_sum = max(max_sum, current_sum)
    
    return max_sum
← Back to All Questions