Maximum Erasure Value

Share

Given an array nums of positive integers, find the maximum sum of a subarray with all unique elements.

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

Solution Approach

Sliding window with a HashSet to track unique elements in current window. When a duplicate is found, shrink the window from the left.

  • Maintain left pointer, running sum, and a HashSet of current window elements.
  • Expand right: if nums[right] already in set, remove nums[left] and advance left (repeat).
  • Add nums[right] to set and sum.
  • Track maximum sum.
Java
import java.util.*;

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        int left = 0, sum = 0, max = 0;
        for (int right = 0; right < nums.length; right++) {
            while (seen.contains(nums[right])) {
                seen.remove(nums[left]);
                sum -= nums[left++];
            }
            seen.add(nums[right]);
            sum += nums[right];
            max = Math.max(max, sum);
        }
        return max;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(N). HashSet