1695. 删除子数组的最大得分 #

标签：数组、哈希表、滑动窗口
难度：中等

题目大意 #

给你一个正整数数组 nums，从中删除一个含有若干不同元素的子数组。删除子数组的「得分」就是子数组各元素之和。

要求：返回只删除一个子数组可获得的最大得分。

解题思路 #

题目要求的是含有不同元素的连续子数组最大和，我们可以用滑动窗口来做，维护一个不包含重复元素的滑动窗口，计算最大的窗口和。具体方法如下：

用滑动窗口 window 来记录不重复的元素个数，window 为哈希表类型。用 window_sum 来记录窗口内子数组元素和，ans 用来维护最大子数组和。设定两个指针：left、right，分别指向滑动窗口的左右边界，保证窗口中没有重复元素。
一开始，left、right 都指向 0。
将最右侧数组元素 nums[right] 加入当前窗口 window 中，记录该元素个数。
如果该窗口中该元素的个数多于 1 个，即 window[s[right]] > 1，则不断右移 left，缩小滑动窗口长度，并更新窗口中对应元素的个数，直到 window[s[right]] <= 1。
维护更新无重复元素的最大子数组和。然后右移 right，直到 right >= len(nums) 结束。
输出无重复元素的最大子数组和。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        window_sum = 0
        left, right = 0, 0
        window = dict()
        ans = 0
        while right < len(nums):
            window_sum += nums[right]
            if nums[right] not in window:
                window[nums[right]] = 1
            else:
                window[nums[right]] += 1

            while window[nums[right]] > 1:
                window[nums[left]] -= 1
                window_sum -= nums[left]
                left += 1
            ans = max(ans, window_sum)
            right += 1
        return ans