< Back




1695. MMaximum Erasure Value

Literally the same problem as a previous one we encountered, maximum subarray with at most k
duplicates or something. In this scenario, we're looking for no duplicates. In order to solve this,
we mantain a set of the numbers we've seen in the input list. We maintain the answer variable,
the current sum, and the left pointer. We could maintain a right pointer, but iterating through
values in a list doesn't necessarily require an index to iterate on.

If we've previously seen the number (it's in the seen set), we remove the number currently pointed to
by the left pointer from the set, subtract the value of the number from the running total, and then
increment the left pointer. We continue to do this until the number is no longer present in the set.

We add the number back to the set - our previous steps were to remove duplicates like discussed, but
also to move the left pointer to the right to maintain or requirement for a subarray of unique
numbers. We add the value of the number to the running total, and retain the max value of the current
answer vs. the running total.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def maximumUniqueSubarray(self, nums: List[int]) -> int:
          seen = set()
          ans = l = curr = 0

          for num in nums:
              while num in seen:
                  seen.remove(nums[l])
                  curr -= nums[l]
                  l += 1

              seen.add(num)
              curr += num
              ans = max(ans, curr)

          return ans


_ Time Complexity:

  O(n) - We iterate through the input once.

_ Space Complexity:

  O(n) - We maintain a set of numbers we've previously seen.