Maximum Erasure Value [Medium] — Sliding Window with HashSet

Problem Statement

You are given an array of positive integers. Select a subarray that has all unique elements, and return the maximum sum of such a subarray.

Input: [4,2,4,5,6] → Output: 17 ([2,4,5,6])
Input: [5,2,1,2,5,2,1,2,5] → Output: 8 ([5,2,1])

Intuition

Sliding window with a set tracking unique elements. Expand right (add to sum and set). When duplicate found, shrink left (remove from sum and set) until duplicate is removed.

Solutions

C++

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

Java

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

Python

def maximumUniqueSubarray(nums: list[int]) -> int:
    seen = set()
    left = s = ans = 0
    for right, val in enumerate(nums):
        while val in seen:
            seen.remove(nums[left])
            s -= nums[left]
            left += 1
        seen.add(val)
        s += val
        ans = max(ans, s)
    return ans

Complexity

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