跳至主要內容

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

ITCharge大约 2 分钟

1695. 删除子数组的最大得分open in new window

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

题目大意

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

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

解题思路

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

  • 用滑动窗口 window 来记录不重复的元素个数,window 为哈希表类型。用 window_sum 来记录窗口内子数组元素和,ans 用来维护最大子数组和。设定两个指针:leftright,分别指向滑动窗口的左右边界,保证窗口中没有重复元素。

  • 一开始,leftright 都指向 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