Code Implementation

class Solution:
    def maximumUniqueSubarray(self, nums):
        seen = set()
        left = 0
        curr_sum = 0
        max_sum = 0
        for right in range(len(nums)):
            while nums[right] in seen:
                seen.remove(nums[left])
                curr_sum -= nums[left]
                left += 1
            seen.add(nums[right])
            curr_sum += nums[right]
            max_sum = max(max_sum, curr_sum)
        return max_sum
      

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        unordered_set<int> seen;
        int left = 0, curr_sum = 0, max_sum = 0;
        for (int right = 0; right < nums.size(); ++right) {
            while (seen.count(nums[right])) {
                seen.erase(nums[left]);
                curr_sum -= nums[left];
                left++;
            }
            seen.insert(nums[right]);
            curr_sum += nums[right];
            max_sum = max(max_sum, curr_sum);
        }
        return max_sum;
    }
};
      

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        int left = 0, currSum = 0, maxSum = 0;
        for (int right = 0; right < nums.length; right++) {
            while (seen.contains(nums[right])) {
                seen.remove(nums[left]);
                currSum -= nums[left];
                left++;
            }
            seen.add(nums[right]);
            currSum += nums[right];
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
    }
}
      

var maximumUniqueSubarray = function(nums) {
    let seen = new Set();
    let left = 0, currSum = 0, maxSum = 0;
    for (let right = 0; right < nums.length; right++) {
        while (seen.has(nums[right])) {
            seen.delete(nums[left]);
            currSum -= nums[left];
            left++;
        }
        seen.add(nums[right]);
        currSum += nums[right];
        maxSum = Math.max(maxSum, currSum);
    }
    return maxSum;
};
      

Problem Description

Given an array of positive integers nums, you can select a subarray (contiguous elements) such that all elements in the subarray are unique (no duplicates). The "erasure value" is defined as the sum of the elements in this subarray. Your goal is to find the maximum erasure value possible — that is, the largest sum of a subarray with all unique elements.

• Each element in the subarray can only be used once; you cannot reuse elements.
• There is always at least one valid solution.
• You must select a contiguous subarray (not just any subset).
• The input nums can have up to 10⁵ elements.

Thought Process

At first glance, you might think of checking every possible subarray, summing its elements, and checking if all elements are unique. However, this brute-force approach is not practical for large arrays because it would require checking an enormous number of subarrays.

Instead, we notice that the problem is about finding the longest (and highest-sum) window with unique elements. This is similar to the classic "Longest Substring Without Repeating Characters" problem, except instead of length, we're maximizing the sum. This suggests using a sliding window technique.

The main challenge is efficiently keeping track of which elements are in the current window and updating the sum as the window moves.

Solution Approach

We'll use a sliding window with two pointers (left and right) and a set to track unique elements within the window.

1. Initialize:
   • A set to keep track of the unique elements in the current window.
   • Two pointers: left (window start) and right (window end).
   • Two sums: curr_sum (sum of current window) and max_sum (global maximum).
2. Expand Window:
   • Move right pointer forward, adding nums[right] to the window.
   • If nums[right] is not in the set, add it to the set and update curr_sum.
   • If nums[right] is already in the set, repeatedly remove nums[left] from the set and subtract from curr_sum, moving left forward until nums[right] is no longer in the set.
3. Update Maximum:
   • After each addition, update max_sum if curr_sum is larger.
4. Continue:
   • Repeat until right reaches the end of the array.
5. Return Result:
   • Return max_sum as the answer.

Why use a set? Because checking for membership and removing elements are both fast (O(1)), which is crucial for efficiency.

Example Walkthrough

Let's walk through an example with nums = [4,2,4,5,6].

1. Start: left = 0, right = 0, seen = {}, curr_sum = 0, max_sum = 0
2. right = 0: Add 4 to set → seen = {4}, curr_sum = 4, max_sum = 4
3. right = 1: Add 2 to set → seen = {2,4}, curr_sum = 6, max_sum = 6
4. right = 2: 4 is already in set. Remove 4 from seen and curr_sum, move left to 1. Now add 4 to set → seen = {2,4}, curr_sum = 6, max_sum = 6
5. right = 3: Add 5 to set → seen = {2,4,5}, curr_sum = 11, max_sum = 11
6. right = 4: Add 6 to set → seen = {2,4,5,6}, curr_sum = 17, max_sum = 17

The result is 17, which comes from the subarray [2,4,5,6].

Time and Space Complexity

• Brute-force approach: For every subarray, check if all elements are unique (O(N²)), and sum the elements (O(N)), leading to O(N³) time — not feasible for large N.
• Optimized sliding window: Each element is added and removed from the set at most once, so the total time is O(N), where N is the length of nums.
• Space complexity: The set can hold up to O(N) elements in the worst case (if all elements are unique).

Summary

The Maximum Erasure Value problem is elegantly solved using a sliding window and a set to track unique elements. By moving the window forward and updating the sum and set efficiently, we avoid redundant work and achieve a fast O(N) solution. The key insight is to recognize the similarity to substring problems and leverage data structures that provide constant-time lookups and removals.