Maximum Erasure Value

medium sliding window hash set

Problem

Given an array of positive integers, find the maximum sum of any contiguous subarray with all unique values.

Inputnums = [4,2,4,5,6]

Output17

Window [2,4,5,6] sums to 17.

nums

def maximum_unique_subarray(nums):
    seen = set()
    left = 0
    cur = best = 0
    for right, x in enumerate(nums):
        while x in seen:
            seen.remove(nums[left])
            cur -= nums[left]
            left += 1
        seen.add(x)
        cur += x
        best = max(best, cur)
    return best

function maximumUniqueSubarray(nums) {
  const seen = new Set();
  let left = 0, cur = 0, best = 0;
  for (let right = 0; right < nums.length; right++) {
    while (seen.has(nums[right])) {
      seen.delete(nums[left]);
      cur -= nums[left];
      left++;
    }
    seen.add(nums[right]);
    cur += nums[right];
    if (cur > best) best = cur;
  }
  return best;
}

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

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

Explanation

We want the largest sum of a contiguous block where every value is unique. A sliding window with a seen set keeps exactly the elements currently in the window, guaranteeing no duplicates.

We move the right pointer over each value x. Before adding it, while x is already in seen, we shrink from the left: remove nums[left] from the set, subtract it from the running sum cur, and advance left. This evicts the old copy of x.

Once the duplicate is gone we add x to the set and to cur, then update best with the largest window sum seen so far.

Example: nums = [4,2,4,5,6]. When the second 4 arrives, the window shrinks past the first 4. The window then becomes [2,4,5,6] with all-unique values summing to 17, which is the answer.

Each element is added and removed at most once, so the algorithm is linear time, using extra space for the set.

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