Problem statement

https://leetcode.com/problems/maximum-erasure-value/

Solution

In this problem we need to find subarray with biggest sum, which has only unique elements. This is in fact almost the same as problem 3. Longest Substring Without Repeating Characters, but here we need to find sum, not length. But idea is exaclty the same:

Let us keep window with elements [beg: end), where first element is included and last one is not. For example [0, 0) is empty window, and [2, 4) is window with 2 elements: 2-th and 3-th.

Let us discuss our algorithm now:

  1. S is set of symbols in our window, we use set to check in O(1) if new symbol inside it or not.
  2. beg = end = 0 in the beginning, so we start with empty window, also ans = 0 and n = len(nums) and sm = 0: sum of elements in window.
  3. Now, we continue, until one of two of our pointers reaches the end. First, we try to extend our window to the right: check s[end] in window and if we can, add it to set, move end pointer to the right and update sm and ans. If we can not add new symbol to set, it means it is already in window set, and we need to move beg pointer to the right, update sm and remove elements from S.

Complexity

We move both of our pointers only to the right, so time complexity is O(n). Space complexity is potentially O(n) as well.

Code

class Solution:
    def maximumUniqueSubarray(self, nums):
        beg, end, S, n, sm = 0, 0, set(), len(nums), 0
        ans = 0
        while end < n:
            if nums[end] not in S:
                sm += nums[end]
                S.add(nums[end])
                end += 1
                ans = max(ans, sm)
            else:
                sm -= nums[beg]
                S.remove(nums[beg])
                beg += 1
        
        return ans

There is also oneliner solution:

class Solution:
    def maximumUniqueSubarray(self, a):
        return (f:=lambda l,r,s,c,b:b if r>=len(a) else f(l+1,r,s.remove(a[l]) or s,c-a[l],b) if a[r] in s else f(l,r+1,s.add(a[r]) or s,c+a[r], max(b,c+a[r])))(0,0,set(),0,0)