子寒的博客
0%

leetcode1695 Maximum Erasure Value 解题报告

发表于 分类于

英文原题

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
2
3
Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].

分析

    滑动窗口问题，也叫虫取法，我做的时候虽然想到了这个方法，但是因为right指针和要加的数那边绕了好久。做法就是用两个指针 left 和 right，right探索前方，发现right所指数字与前面重复了就把left 向前靠，直到left到了重复的那个数字为止。

python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        left, right = 0, 0
        res = 0
        tmp = 0
        numSet = set([])
        
        while right < len(nums):
            if nums[right] not in numSet:
                tmp += nums[right]
                numSet.add(nums[right])
                res = max(res, tmp)
            else:
                while left <= right:
                    if nums[left] == nums[right]:
                        left += 1
                        break
                    else:
                        numSet.remove(nums[left])
                        tmp -= nums[left]
                        left += 1
            right += 1
        return res