Description

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

Solution

1. The naive approach would be check all possible subarray with unique elements and get the maximum score among them. There are O(n^2) subarray. Check the uniqueness take O(n). So the total complexity is O(n^3). But can we do better? Yes.

2. Pay attention to the constraint. We have an array with all elements positive. If means if we let the sliding window [l , r) be the maximum subarray without duplicate. Then [s, r) with s > l will have smaller score than [l , r). So [l , r + 1) will have a duplicate. Then we need to increment l, we don’t need to check [l + 1, r) since [l + 1, r) has smaller score than [l , r) based on positive constraint. We increment l until nums[r + 1] is not in the set. We maintain a set to check the uniqueness of subarray elements.

Below is the implementation

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        '''
        let [l, r) be the largest sliding window containing unique elements. Since the array contains only positive integers. Any subarray inside [l , r) will have smaller scores than [l, r). Then move the sliding window to the next position [l + 1, r + 1). We don't need to check [l + 1, r) since it won't contain any duplicates. Therefore, it has smaller score than [l, r)
        '''
        n = len(nums)
        l = 0
        r = 0
        st = set([])
        ts = 0
        ret = float('-inf')
        while r < n:
            if nums[r] not in st:
                ts += nums[r]
                ret = ts if ts > ret else ret
                st.add(nums[r])
                r += 1
            else:
                st.remove(nums[l])
                ts -= nums[l]
                l += 1
        return ret