1695 - Maximum Erasure Value

Difficulty: Medium | Pattern: Sliding Window | Company tags: Amazon, Spotify

Problem Statement

You are given an array of positive integers nums. You want to select a subarray of nums. The score of a subarray starting at index l and ending at index r is nums[l] + nums[l+1] + ... + nums[r].

You can only take a subarray where every element appears at most once.

Return the maximum score of a subarray of nums.

Example 1:

Input: nums = [4,2,4,5,6]
Output: 17
Explanation: Subarray [2,4,5,6] → score = 17

Example 2:

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: [5,2,1] or [1,2,5] → score = 8

Approach: Sliding Window with Set — O(n)

Key insight: Maintain a window with no duplicate elements. When a duplicate is about to enter, shrink the window from the left until the duplicate is removed.

def maximumUniqueSubarray(nums: list[int]) -> int:
    seen = set()
    left = 0
    current_sum = 0
    max_sum = 0
    
    for right in range(len(nums)):
        while nums[right] in seen:
            seen.remove(nums[left])
            current_sum -= nums[left]
            left += 1
        
        seen.add(nums[right])
        current_sum += nums[right]
        max_sum = max(max_sum, current_sum)
    
    return max_sum

Optimized: Dict (O(1) jump)

def maximumUniqueSubarray(nums: list[int]) -> int:
    last_seen = {}
    left = 0
    current_sum = 0
    max_sum = 0
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i+1] = prefix[i] + x
    
    for right, x in enumerate(nums):
        if x in last_seen and last_seen[x] >= left:
            left = last_seen[x] + 1
        last_seen[x] = right
        max_sum = max(max_sum, prefix[right+1] - prefix[left])
    
    return max_sum

Algorithm Flow

Dry Run

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

right	nums[right]	left	window	sum
0	4	0	[4]	4
1	2	0	[4,2]	6
2	4	1	[2,4] (remove 4 from left)	6
3	5	1	[2,4,5]	11
4	6	1	[2,4,5,6]	17

max = 17 ✓

Edge Cases

• All unique → entire array is the answer
• All same → each single element; return that element
• Single element → return it

Complexity

• Time: O(n) — each element added and removed at most once
• Space: O(k) where k = distinct elements in window

Note: This problem is essentially LeetCode 3 (Longest Substring Without Repeating Characters) but tracks sum instead of length.

Key Terms

Term	Definition
Sliding window	A contiguous range [left, right] over the array that expands and shrinks to maintain an invariant.
Prefix sum	prefix[i] = sum of first i elements; lets you get any range sum in O(1).
Two pointers	left and right indices moved independently to track window boundaries in O(n) total work.
Amortized O(n)	Each element enters and leaves the window at most once, so total pointer moves are bounded by 2n.

FAQ

1. Can this be solved without extra space beyond O(k)? No — you need at least a set/dict to detect duplicates in the current window; k is the number of distinct values in the window, bounded by n.
2. What if the array is empty? Return 0 immediately; the loop never executes and max_sum stays 0.
3. What if all elements are unique? The window never shrinks, and the answer is the sum of the entire array.
4. How would this change if we wanted the longest such subarray instead of max sum? Track right - left + 1 instead of current_sum/prefix difference — same sliding window skeleton.
5. Why does the dict version avoid removing elements one by one? Because it jumps left directly to last_seen[x] + 1 instead of incrementally removing from the set, turning multiple removals into one O(1) jump.

Quick Revision

• Pattern: sliding window / two pointers for "no duplicate" constraint.
• Maintain a seen set (or last_seen dict) of elements currently in the window.
• On duplicate, shrink from the left until the duplicate is gone (set version) or jump left directly (dict version).
• Track running sum incrementally; avoid recomputation.
• max_sum updates after every valid expansion.
• Time: O(n) because each index enters/leaves the window once.
• Space: O(k) for the set/dict, k ≤ n.
• Same skeleton as LeetCode 3 (Longest Substring Without Repeating Characters), swapping "length" for "sum".
• Edge cases: empty array → 0; all identical elements → answer is the max single element.

Related Problems

• Sliding window with duplicates: see LeetCode 3 (Longest Substring Without Repeating Characters) — same shrink-on-duplicate pattern, tracked by length instead of sum.
• 1852-DistinctNumbersInEachSubarray.md — fixed-size window with duplicate tracking.
• 3-LongestSubstringWithoutRepeatingCharacters.md — the classic version of this same pattern.