[Leetcode] 1695. Maximum Erasure Value

https://leetcode.com/problems/maximum-erasure-value/description/?envType=daily-question&envId=2025-07-22

initial

solved it its typical sliding window

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        check = set()
        left,right=0,0
        length=len(nums)
        tmp=0
        ans=0
        while right<length:
            if nums[right] not in check:
                tmp+=nums[right]
                check.add(nums[right])
                right+=1
            else:
                ans=max(ans,tmp)
                while nums[right] in check:
                    tmp-=nums[left]
                    check.remove(nums[left])
                    left+=1
        ans=max(ans,tmp)
        return ans

sol

but instead of iter left by 1 step until we remove the duplicate, we can store the last index of that duplicate values in a hashmap. Then when we see if the current iter is that duplicate number, we immediately shift left pointer to that duplicate values' index +1. Why do we max(left) tho? It is to prevent left pointer from shifting backward.

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        check = set()
        left,right=0,0
        length=len(nums)
        tmp=0
        ans=0
        prefix=[0 for _ in range(length+1)]
        dic={}
        for right in range(length):
            prefix[right+1]=prefix[right]+nums[right]
            if nums[right] in dic:
                left = max(dic[nums[right]]+1,left)
            ans=max(ans,prefix[right+1]-prefix[left])
            dic[nums[right]] = right
        return ans

complexity

n time n space