Maximum Erasure Value — Longest Unique Subarray Sum

Problem Statement#

Given an array of positive integers nums, find the maximum sum of any contiguous subarray whose elements are all distinct.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

Input:  nums = [4,2,4,5,6]
Output: 17

Input:  nums = [5,2,1,2,5,2,1,2,5]
Output: 8

Why This Problem Matters#

LeetCode 1695 is one of the cleanest sliding window problems for testing whether candidates understand the difference between maximizing length and maximizing sum. Google, Amazon, and Cisco have asked variants of it.

The problem also rules out negative numbers, which keeps the running sum monotonically increasing as the window grows. That subtle constraint is what makes the simple "expand-and-shrink" template work; without it you would need prefix sums and a different approach.

You will see the same window-with-set technique in LC 3 (Longest Substring Without Repeating Characters). After this problem, that one becomes a five-minute warmup.

The Core Insight#

Use a HashSet to track values currently inside the window and a running sum. Expand right one element at a time. If the new element is already in the set, shrink from the left — removing values from the set and subtracting from the sum — until the duplicate is gone. After every expansion, update the answer.

The trick is to perform the shrink before adding the new element rather than after. If you add first you must guard against the just-added duplicate while shrinking, which complicates the loop.

This is the canonical "shrinkable window with uniqueness invariant" template; it works for any maximization where adding an element can violate constraints that shrinking from the left can restore.

Visual Dry Run#

Trace nums = [4, 2, 4, 5, 6].

Step 3 shows the duplicate 4 triggering a shrink that removes the original 4 before adding the new one.

Solution (Optimal)#

class Solution:
    def maximumUniqueSubarray(self, nums: list[int]) -> int:
        seen = set()
        left = 0
        running = 0
        best = 0
 
        for right, v in enumerate(nums):
            while v in seen:
                seen.remove(nums[left])
                running -= nums[left]
                left += 1
            seen.add(v)
            running += v
            best = max(best, running)
 
        return best

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

Time: O(n) — each index enters and leaves the set at most once. Space: O(n) — set holds up to all distinct values.

Common Mistakes#

• Adding the new element to the set before shrinking. Now the duplicate detection breaks because the set always contains it.
• Forgetting to subtract from running while shrinking. The sum becomes stale and you over-report the answer.
• Using a HashMap of indices and jumping left directly. Subtracting the skipped elements is then easy to forget.
• Returning length instead of sum — easy slip-up because the template feels like LC 3.
• Initializing best to nums[0] when the array is non-empty is fine, but starting at zero also works because all values are positive.

Interview Tips#

• State the invariant: "the window always contains distinct values".
• Emphasize that shrinking comes before adding the new element.
• Mention that you maintain a running sum to avoid recomputing the window sum each iteration.
• Sanity-check with the all-same input [5, 5, 5] — answer should be 5.
• Compare and contrast with LC 3 (length, not sum) so the interviewer sees you have both templates.

Follow-up Questions#

• What if values can be negative? Hint: shrinking does not necessarily restore optimality; need different approach.
• Return the actual subarray. Hint: track left and right when best updates.
• What if duplicates are allowed up to k times? Hint: change set to a count map and shrink while count exceeds k.
• Streaming version. Hint: same code; the algorithm is already streaming-friendly.
• What if you can delete one element to maximize uniqueness? Hint: variation of the standard template with one allowance.

Key Takeaways#

• LeetCode 1695 maximizes the sum of a contiguous subarray with all unique values.
• Use a HashSet plus a shrinkable sliding window and a running sum.
• Shrink before adding the new element to keep the duplicate-detection logic clean.
• Time O(n), space O(n) for the set.
• Positive-values-only constraint is what allows the greedy expand-shrink template to work.
• Same template solves LC 3 (Longest Substring Without Repeating Characters) for length.
• Asked at Google, Amazon, and Cisco interviews.