1695. 删除子数组的最大得分
大约 2 分钟
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)
结束。输出无重复元素的最大子数组和。
代码
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