1695: Maximum-Erasure-Value
Medium

A simply sliding window algorithm that requires you to iterate through all the elements inside nums until we reach a duplicate value (we can track this using a hashmap).

Basically, we “extend” the RHS of the sliding window until we reach a duplicate value. When we do reach a duplicate value, we shrink the sliding window by shifting the LHS of the sliding window to the right. Thus, we can ensure our subarray ONLY contains unique numbers.

Then, if we keep a running sum of all the elements inside the sliding window, and keep track of the maximum possible running sum, we would be able to find the maximum score.

code

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int l = 0;
        int sum = 0;
        int ans = 0;
        int uniqueNums[10001] = {0};
        for (int& num : nums) {
            if (uniqueNums[num] == 1) {
                ans = max(ans, sum);
                while (nums[l] != num) {
                    --uniqueNums[nums[l]];
                    sum -= nums[l];
                    ++l;
                }
                ++l;
            } else {
                ++uniqueNums[num];
                sum += num;
            }
        }
        ans = max(ans, sum);

        return ans;
    }
};

complexity

time taken