1695. Maximum Erasure ValueSolution

1695. Maximum Erasure Value

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

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

My Solutions:

这道题需要找在nums中的一个subarray which only contains unique elements. 用sliding window记录满足条件的array，l代表sliding window的左端，r代表右端。

• 如果当前数字n没有见过，就把此数字和他的index记录在seen里，更新sum和ans。

• 如果此数字见过，比如example2中走到[5,2,1,2]，此时index=3, 数字2已经在index=1时出现过。把从指针l所在的数字（index=0）到这个数字之前所在位置（index=1）中间位置的所有数字从seen里删掉，此时seen里只剩下数字1。更新sum（从8变成1）和l（变成数字1所在的index=2）。

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        // l代表sliding window的最左端
        int l = 0, sum = 0, ans = 0;
        
        // 用map记录见过的数字和其index
        Map<Integer, Integer> seen = new HashMap<>();
    
        for (int r = 0; r < nums.length; r++){
            int n = nums[r];
            if (seen.containsKey(n)) {
                int index = seen.get(n);
                while (l <= index) {
                    seen.remove(nums[l]);
                    sum -= nums[l];
                    l++;
                }
            }
            seen.put(n, r);
            sum += n;
            ans = Math.max(ans,sum);
        }
        return ans;
    }
}