1695.-maximum-erasure-value.md

1695. Maximum Erasure Value

• Medium

• 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).

Analysis

The idea is similar to the previous questions about same letters/digts in an array. We solve this by creating an dictionary of "seen". In it, we put the value of current sum. And when we run into the same digit, or what i call a 'match', we update the dictionary to the current sum.

Now the sum we are looking for is the sum of digits after the latest match, so we need an variable to record the latest match, and then subtract that from the current sum. That gives us the sum of the current subarray.

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        currmax=0
        sumi=0
        seen={}
        latest=0
        for i in nums:
            sumi+=i
            if i in seen:
                latest=max(seen[i],latest)
            currmax=max(currmax,sumi-latest)
            #print(sumi,latest,currmax)
            seen[i]=sumi

        return currmax