Maximum Erasure Value

Problem Statement

You are tasked with identifying a contiguous subarray from a given array of positive integers, where all elements are unique. The objective is to find such a subarray such that if you were to 'erase' this part of the array, the sum of its values would be maximized. The score of erasing a subarray is computed by summing up all its elements. Your goal is to compute the maximum score possible by erasing exactly one subarray which must consist exclusively of unique elements.

Examples

Example 1

Input:

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

Output:

17

Explanation:

The optimal subarray here is [2,4,5,6].

Example 2

Input:

nums = [5,2,1,2,5,2,1,2,5]

Output:

8

Explanation:

The optimal subarray here is [5,2,1] or [1,2,5].

Constraints

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

Approach and Intuition

Given the nature of the problem, with its focus on maximizing a sum of unique-element subarrays, a logical approach involves the use of a sliding window technique combined with tracking mechanisms for elements to ensure uniqueness. Here's a step-by-step breakdown of the proposed method:

1. Initialize two pointers to define the window - commonly left and right pointers.
2. Use a hash map or set to keep track of the elements in the current window and ensure all elements are unique.
3. Expand the right pointer to extend the window until a duplicate element is encountered or the end of the array is reached.
4. As you expand the window, keep updating the current sum of the window.
5. When a duplicate is encountered, move the left pointer to shrink the window until the duplicate is excluded, ensuring the uniqueness of elements within the window.
6. Continuously update and track the maximum sum encountered.
7. Continue this process until the right pointer has traversed the entire array.

This technique leverages the efficiency of the sliding window to check each element once, adjusting the window boundaries as duplicates are encountered and removed. By doing this, we ensure that the time complexity is efficient, ideally near linear relative to the size of the input array.

The intuition behind using a sliding window here is due to the need for exploring subarrays of variable sizes to find the maximum sum possible. Tracking the largest sum during this traversal allows for efficient determination of the optimal score in a single pass of the array, minimizing unnecessary recalculations.

Solutions

class Solution {
public:
    int maxUniqueSubarraySum(vector<int>& nums) {
        int length = nums.size(), maxSum = 0, low = 0, maxVal = 10001;
        vector<int> indexes(maxVal, -1);
        vector<int> cumulativeSum(length + 1, 0);
        for (int high = 0; high < length; high++) {
            int val = nums[high];
            cumulativeSum[high + 1] = cumulativeSum[high] + val;
            if (indexes[val] >= 0) {
                low = max(low, indexes[val] + 1);
            }
            maxSum = max(maxSum, cumulativeSum[high + 1] - cumulativeSum[low]);
            indexes[val] = high;
        }
        return maxSum;
    }
};