Problem Description

• 1695. Maximum Erasure Value

This problem asks us to find the maximum sum of a contiguous subarray where all elements are unique (no duplicates). We need to identify the subarray with unique elements that has the largest sum and return that sum.

The key constraints are:

• The subarray must be contiguous
• All elements in the subarray must be unique
• We want to maximize the sum of elements

Algorithm Walkthrough

This solution uses a sliding window approach with prefix sums for efficient range sum calculation:

Data Structures:

• lastIndex[]: Array to track the most recent index where each value appeared (size 10001 to handle constraint that nums[i] ≤ 10^4)
• prefixSum[]: Cumulative sum array for O(1) range sum queries
• l: Left boundary of the current valid window (initially -1)
• sum: Maximum sum found so far

Algorithm Steps:

1. Initialize tracking arrays: Set all positions in lastIndex to -1 (indicating no previous occurrence)

2. Iterate through array with right pointer r:

   • Build prefix sum: prefixSum[r+1] = nums[r] + prefixSum[r]

3. Handle duplicates: If nums[r] has appeared before (lastIndex[nums[r]] >= 0):

   • Move left boundary l to the maximum of current l and the last occurrence of nums[r]
   • This ensures the window [l+1, r] contains only unique elements

4. Calculate current window sum: Use prefix sums for O(1) calculation:

   • Current sum = prefixSum[r+1] - prefixSum[l+1]
   • Update maximum sum if current sum is larger

5. Update last occurrence: Set lastIndex[nums[r]] = r

Example trace with [4,2,4,5,6]:

• r=0, nums[0]=4: l=-1, sum=4, lastIndex[4]=0
• r=1, nums[1]=2: l=-1, sum=6, lastIndex[2]=1
• r=2, nums[2]=4: 4 seen at index 0, so l=max(-1,0)=0, sum=max(6,6)=6, lastIndex[4]=2
• r=3, nums[3]=5: l=0, sum=max(6,11)=11, lastIndex[5]=3
• r=4, nums[4]=6: l=0, sum=max(11,17)=17, lastIndex[6]=4

The optimal subarray [2,4,5,6] from indices 1-4 gives sum 17.

Full Solution(Java)

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int[] lastIndex = new int[10001];
        for (int i = 0; i < lastIndex.length; i++) {
            lastIndex[i] = -1;
        }
        int l = -1, sum = 0;
        int[] prefixSum = new int[nums.length+1];
        for (int r = 0; r < nums.length; r++) {
            prefixSum[r+1] = nums[r] + prefixSum[r];
            if (lastIndex[nums[r]] >= 0) {
                l = Math.max(l, lastIndex[nums[r]]);
            }
            sum = Math.max(sum, prefixSum[r+1] - prefixSum[l+1]);
            lastIndex[nums[r]] = r;
        }
        return sum;

    }
}

Complexity Analysis

Time Complexity: O(n)

• Single pass through the array with constant work per element
• Prefix sum calculation: O(1) per element
• Duplicate checking and window adjustment: O(1) per element

Space Complexity: O(n)

• lastIndex array: O(10001) = O(1) since it's bounded by the constraint
• prefixSum array: O(n+1) = O(n)
• Overall: O(n) due to the prefix sum array

The solution efficiently maintains a sliding window of unique elements while using prefix sums to avoid recalculating subarray sums, making it optimal for this problem.