Understanding the Problem

Given an array of integers nums, our task is to find the maximum sum of a contiguous subarray containing only unique elements.

Approach

We can solve this problem using a sliding window approach. We’ll maintain two pointers, start and end, to define the current subarray. Additionally, we’ll use a HashSet to keep track of the unique elements in the current subarray.

As we iterate through the array, we’ll adjust the window size based on whether the current element is already present in the HashSet or not. If the element is unique, we’ll expand the window by moving the end pointer forward and updating the sum. If the element is not unique, we’ll shrink the window by moving the start pointer forward until the duplicate element is removed from the window.

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        /* 
            Start, end pointer and a set.
            Increase end till the set has unique element, if duplicate found increment start till
            that element is removed from the list
        */

        int start = 0, end = 0, sum = 0, max = Integer.MIN_VALUE;
        HashSet<Integer> set = new HashSet<Integer>();
        while(end < nums.length) {
            if (!set.contains(nums[end])) {
                sum += nums[end];
                max = Math.max(max, sum);
                set.add(nums[end]);
                end++;
            } else {
                while(set.contains(nums[end])) {
                    sum -= nums[start];
                    set.remove(nums[start]);
                    start++;
                }
            }
        }
        return max;
    }
}

Read Also: 76. Minimum Window Substring

Explanation

• We initialize the start, end pointers, and the sum to 0, and the maximum value as the minimum integer value.
• We iterate through the array using the end pointer.
• If the current element is not present in the HashSet, we add it to the HashSet, update the sum, and check if it’s the maximum sum encountered so far.
• If the current element is already present in the HashSet, we remove elements from the window by moving the start pointer forward until the duplicate element is removed.
• We update the maximum sum whenever we encounter a unique subarray.

https://leetcode.com/problems/maximum-erasure-value/