Problem Description

You have an array of positive integers nums. Your task is to find and erase a subarray that contains only unique elements (no duplicates). When you erase a subarray, you get a score equal to the sum of all elements in that subarray.

A subarray is a contiguous portion of the original array - it must be a sequence of consecutive elements like a[l], a[l+1], ..., a[r] for some indices l and r.

The goal is to find the maximum possible score you can achieve by erasing exactly one such subarray where all elements are distinct.

For example:

• If nums = [4,2,4,5,6], one valid subarray with unique elements is [2,4,5,6] with sum = 17
• Another valid subarray is [4,2] with sum = 6
• The subarray [4,2,4] is NOT valid because it contains duplicate 4s

You need to return the maximum sum among all possible subarrays that contain only unique elements.

Intuition

The key insight is that we want to find the maximum sum of a contiguous subarray with all unique elements. This is essentially a sliding window problem, but we need to handle the constraint of uniqueness.

Think of it this way: as we scan through the array from left to right, we can maintain a "valid window" that contains only unique elements. Whenever we encounter a duplicate, we need to shrink our window from the left until the duplicate is removed.

For example, if we have [4, 2, 4, 5, 6] and we're at the second 4 (index 2), we know that any subarray containing both 4s is invalid. So the earliest valid starting point for our current window must be after the first 4 (index 0).

To efficiently track this, we can record the last occurrence position of each number. When we see a number v at position i, if we've seen v before at position d[v], then our valid window can only start from position d[v] + 1 or later.

The prefix sum technique comes into play for calculating subarray sums quickly. Instead of recalculating the sum each time, we can use s[i] - s[j] to get the sum of elements from index j to i-1 in constant time.

The variable j acts as a "barrier" - it represents the leftmost position where our current valid window can start. As we move through the array, j only moves rightward (or stays the same) when we encounter duplicates, ensuring we always maintain a valid window with unique elements.

At each position, we calculate the sum of the current valid window and keep track of the maximum sum seen so far.

Learn more about Sliding Window patterns.

Solution Approach

The solution uses a combination of hash table/array for tracking positions and prefix sum for efficient sum calculation.

Data Structures Used:

1. d: An array (or hash table) where d[v] stores the last occurrence index of value v. We initialize it with size max(nums) + 1 for direct indexing.
2. s: A prefix sum array where s[i] represents the sum of all elements from index 0 to i-1. We use accumulate(nums, initial=0) to build this.
3. j: A pointer tracking the leftmost valid starting position of our current window.
4. ans: Stores the maximum sum found so far.

Algorithm Steps:

1. Initialize data structures:

   • Create array d with zeros, sized to accommodate the maximum value in nums
   • Build prefix sum array s where s[0] = 0 and s[i] = s[i-1] + nums[i-1]
   • Set ans = 0 and j = 0

2. Iterate through the array: For each element v at position i (1-indexed):

   a. Update the window's left boundary:

   • j = max(j, d[v])
   • If d[v] > 0, it means we've seen v before at position d[v]
   • We must start our window after the previous occurrence to maintain uniqueness

   b. Calculate current window sum:

   • Sum from position j to i-1 (0-indexed) = s[i] - s[j]
   • Update ans = max(ans, s[i] - s[j])

   c. Record current position:

   • d[v] = i to mark that value v was last seen at position i

3. Return the maximum sum found

Example Walkthrough: For nums = [4, 2, 4, 5, 6]:

• Initially: d = [0,0,0,0,0,0,0], s = [0,4,6,10,15,21], j = 0
• i=1, v=4: j = max(0, 0) = 0, sum = 6-0 = 6, d[4] = 1
• i=2, v=2: j = max(0, 0) = 0, sum = 6-0 = 6, d[2] = 2
• i=3, v=4: j = max(0, 1) = 1, sum = 10-4 = 6, d[4] = 3
• i=4, v=5: j = max(1, 0) = 1, sum = 15-4 = 11, d[5] = 4
• i=5, v=6: j = max(1, 0) = 1, sum = 21-4 = 17, d[6] = 5
• Maximum sum = 17

The time complexity is O(n) as we make a single pass through the array, and space complexity is O(m) where m is the maximum value in the array.

Example Walkthrough

Let's walk through the solution with nums = [1, 2, 1, 3]:

Initial Setup:

• Create position tracker: d = [0, 0, 0, 0] (size = max(nums) + 1 = 4)
• Build prefix sum: s = [0, 1, 3, 4, 7]
  • s[0] = 0
  • s[1] = 0 + 1 = 1
  • s[2] = 1 + 2 = 3
  • s[3] = 3 + 1 = 4
  • s[4] = 4 + 3 = 7
• Initialize: j = 0 (left boundary), ans = 0 (max sum)

Step-by-step Processing:

Position i=1, value v=1:

• Check last occurrence: d[1] = 0 (never seen)
• Update left boundary: j = max(0, 0) = 0
• Valid window: indices [0] contains [1]
• Window sum: s[1] - s[0] = 1 - 0 = 1
• Update max: ans = max(0, 1) = 1
• Mark position: d[1] = 1

Position i=2, value v=2:

• Check last occurrence: d[2] = 0 (never seen)
• Update left boundary: j = max(0, 0) = 0
• Valid window: indices [0,1] contains [1,2]
• Window sum: s[2] - s[0] = 3 - 0 = 3
• Update max: ans = max(1, 3) = 3
• Mark position: d[2] = 2

Position i=3, value v=1:

• Check last occurrence: d[1] = 1 (seen at position 1!)
• Update left boundary: j = max(0, 1) = 1
• Valid window: indices [1,2] contains [2,1]
• Window sum: s[3] - s[1] = 4 - 1 = 3
• Update max: ans = max(3, 3) = 3
• Mark position: d[1] = 3

Position i=4, value v=3:

• Check last occurrence: d[3] = 0 (never seen)
• Update left boundary: j = max(1, 0) = 1
• Valid window: indices [1,2,3] contains [2,1,3]
• Window sum: s[4] - s[1] = 7 - 1 = 6
• Update max: ans = max(3, 6) = 6
• Mark position: d[3] = 4

Result: Maximum sum = 6 (subarray [2,1,3])

The key insight: when we encounter a duplicate (the second 1 at position 3), we automatically adjust our window's left boundary to exclude the first occurrence, maintaining the uniqueness constraint while maximizing the sum.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m), where n is the length of the array nums and m is the maximum value in nums.

• Finding max(nums) takes O(n) time
• Creating the prefix sum array using accumulate takes O(n) time
• The main loop iterates through all n elements once, with each iteration performing constant time operations: O(n)
• Total: O(n) + O(n) + O(n) = O(n) when m is considered bounded or small relative to n

However, if we consider m (the maximum value) as an independent variable, the complexity becomes O(n + m) due to the array initialization d = [0] * (max(nums) + 1).

Space Complexity: O(n + m), where n is the length of the array nums and m is the maximum value in nums.

• The array d has size max(nums) + 1, which requires O(m) space
• The prefix sum array s has size n + 1, which requires O(n) space
• Other variables (ans, j, i, v) use O(1) space
• Total: O(n + m)

When the maximum value m is bounded by a constant or is proportional to n, both complexities simplify to O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Memory Inefficiency with Large Values

The current solution creates an array of size max(nums) + 1, which can be extremely memory-inefficient when the input contains large values. For instance, if nums = [1, 1000000], the solution allocates an array of size 1,000,001 just to track two values.

Solution: Use a dictionary/hashmap instead of an array for tracking last seen positions:

last_seen_index = {}  # Instead of [0] * (max(nums) + 1)

# When accessing, use .get() with default value
left_boundary = max(left_boundary, last_seen_index.get(current_value, 0))

2. Off-by-One Errors with Index Management

The solution mixes 0-indexed arrays with 1-indexed position tracking, which can easily lead to confusion. The enumerate(nums, 1) starts counting from 1, while array indices start from 0. This discrepancy makes the code harder to debug and maintain.

Solution: Stick to consistent 0-based indexing throughout:

for i in range(len(nums)):
    current_value = nums[i]
    # Update left boundary to be the index AFTER the last occurrence
    if current_value in last_seen_index:
        left_boundary = max(left_boundary, last_seen_index[current_value] + 1)
  
    # Calculate sum from left_boundary to i (inclusive)
    current_sum = prefix_sums[i + 1] - prefix_sums[left_boundary]
    max_sum = max(max_sum, current_sum)
  
    # Store current index (not position)
    last_seen_index[current_value] = i

3. Integer Overflow in Other Languages

While Python handles arbitrarily large integers, implementing this solution in languages like Java or C++ could cause integer overflow when calculating sums for large arrays with large values.

Solution: Use appropriate data types (e.g., long long in C++ or long in Java) for sum calculations and consider the constraints carefully.

4. Incorrect Sliding Window Updates

A common mistake is forgetting to update the left boundary correctly when duplicates are found. Some might incorrectly set left_boundary = last_seen_index[current_value] instead of taking the maximum with the current left boundary, which could move the window backward illegally.

Solution: Always ensure the window only moves forward:

# Correct: window never moves backward
left_boundary = max(left_boundary, last_seen_index[current_value])

# Incorrect: could move window backward
# left_boundary = last_seen_index[current_value]