Maximum Erasure Value

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;
    }
};

In this solution, the goal is to find the maximum sum of any contiguous subarray in a given list of integers, where all integers are unique within the subarray. The approach utilizes a sliding window technique combined with a hashmap to keep track of the most recent indices of each number within the array.

Follow these steps to understand the method implemented in the C++ code:

1. Initialize variables for the size of the array (length), maximum sum identified (maxSum), the starting point of the sliding window (low), and establish a limit (maxVal) to create a sufficiently large vector to keep track of indices.
2. Create two vectors: indexes initialized with -1 to keep track of the latest index of each number, and cumulativeSum to store the running sum of elements up to current index for easy calculation of sum within a range.
3. Iterate through the array using an index (high) that represents the end of the current window:
   • Update cumulativeSum for current index by adding the value at nums[high].
   • If the current number was seen before (i.e., indexes[nums[high]] is not -1), update low to ensure no numbers are repeated in the current subarray.
   • Calculate the sum of the current subarray by subtracting the cumulative sum at the start of the window (low) from that at the end (high + 1). Update maxSum if this new sum is greater.
   • Update the last seen index of current number in indexes.
4. Return maxSum as the result which holds the maximum sum of a unique-element subarray.

With this efficient approach, each element in the array is processed in constant time, leading to a solution that scales linearly with the size of the input array.

class Solution {
    public int maxUniqueSubarray(int[] elements) {
        int len = elements.length, maxVal = 10001;
        int[] lastIndex = new int[maxVal];
        int[] accumSum = new int[len + 1];
        Arrays.fill(lastIndex, -1);
        int maxSum = 0, windowStart = 0;
        for (int windowEnd = 0; windowEnd < len; windowEnd++) {
            int element = elements[windowEnd];
            accumSum[windowEnd + 1] = accumSum[windowEnd] + element;
            if (lastIndex[element] != -1) {
                windowStart = Math.max(windowStart, lastIndex[element] + 1);
            }
            maxSum = Math.max(maxSum, accumSum[windowEnd + 1] - accumSum[windowStart]);
            lastIndex[element] = windowEnd;
        }
        return maxSum;
    }
}

The provided Java code implements a solution to find the maximum score of a unique subarray from a given array of integers. The objective is to select a contiguous subarray such that no value appears more than once, and its sum is the highest possible. The approach taken can be summarized as follows:

• Initialize an array lastIndex to store the last occurrence index of each element within the range of potential values in the elements array. The length of lastIndex is set to a constant maxVal, considering the maximum possible value in the elements array +1 to handle the indexing conveniently.
• Utilize an auxiliary array accumSum to hold the accumulative sum of the elements, which aids in efficiently calculating the sum of any subarray.
• Use two pointers, windowStart and windowEnd, to manage the sliding window's bounds.
• Iterate through the elements using windowEnd. During each iteration:
  • Update the accumulative sum in accumSum.
  • If the current element has appeared earlier (i.e., its index is recorded in lastIndex), adjust windowStart to ensure all elements in the current window are unique.
  • Calculate the current subarray's sum by subtracting the accumulative sum at windowStart from the accumulative sum at windowEnd + 1. Update maxSum if the current subarray's sum is greater.
  • Update the lastIndex of the current element to the current windowEnd to track its most recent appearance.
• The algorithm ultimately returns maxSum, which is the maximum sum of any unique subarray found during the iteration.

This approach efficiently tracks and updates the required values using a combination of auxiliary data structures and a sliding window technique, ensuring that each element contributes to at most one unique subarray in consideration for the maximum sum.