华为 OD 训练营 · 题解精讲
LC1695. 删除子数组的最大分数
配套讲解：视频讲解 ↗
LC1695. 删除子数组的最大分数 视频地址：https://uha.xet.tech/s/2AtIE4
题目描述
给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。 返回 只删除一个 子数组可获得的 最大得分 。 如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。 示例 1： 输入：nums = [4,2,4,5,6] 输出：17 解释：最优子数组是 [2,4,5,6] 示例 2： 输入：nums = [5,2,1,2,5,2,1,2,5] 输出：8 解释：最优子数组是 [5,2,1] 或 [1,2,5] 提示： 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^4
题目解析
解题思路
本题要求删除一个不含重复元素的子数组，使得子数组元素和最大。等价于寻找数组中不含重复元素的最大和子数组。
由于数组元素均为正数，子数组越长和越大，但必须保证元素不重复。因此采用不定长滑动窗口（双指针）配合哈希集合来维护一个无重复元素的窗口。
核心思路：右指针 end 不断向右扩展，将新元素加入窗口；若新元素已在窗口中（重复），则移动左指针 start 逐步移除左侧元素，直到窗口中不再有该重复元素。窗口内始终维护元素和 sums，并不断更新最大和 largest。
关键步骤
1. 初始化：start = 0，sums = 0，largest = 0，hash 为空集合。 2. 遍历数组，end 从 0 到 len(nums)-1：
- 若
nums[end]已在hash中，执行 while 循环： sums -= nums[start]- 从
hash中移除nums[start] start += 1- 将
nums[end]加入hash sums += nums[end]largest = max(largest, sums)
3. 返回 largest。
示意图（以 [4,2,4,5,6] 为例）：
初始: start=0, end=0, 窗口=[4], sum=4, largest=4
end=1: 窗口=[4,2], sum=6, largest=6
end=2: nums[2]=4 重复，移除 nums[0]=4 → 窗口=[2,4], sum=6, largest=6
end=3: 窗口=[2,4,5], sum=11, largest=11
end=4: 窗口=[2,4,5,6], sum=17, largest=17复杂度分析
- 时间复杂度：O(N)，每个元素最多被左右指针各访问一次，哈希集合的增删查操作均为 O(1)。
- 空间复杂度：O(N)，最坏情况下哈希集合存储整个数组（所有元素互异）。
参考代码
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
# 滑动窗口模板化解题，五步走策略
# 【1、定义需要维护的变量】
# 对于此题来说，需要维护当前滑动窗口的元素和、滑动过程中得出的最大得分
# 一开始，滑动窗口没有元素，元素和为 0
sums = 0
# 由于数组都是正数，所以可以初始化为 0
largest = 0
# 同时又涉及去重，因此需要一个哈希表
hash = set()
# 【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
# 窗口的左端位置从 0 开始
start = 0
# 窗口的右端位置从 0 开始，可以一直移动到尾部
for end in range(len(nums)) :
# 【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
# 【4、如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题】
# 如果当前窗口不合法时, 用一个 while 去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
# 如果哈希表中存储了即将加入滑动窗口的元素
while nums[end] in hash :
# 那么需要不断的把窗口左边的元素移除窗口
# 元素和需要减去移除的值
sums -= nums[start]
# 把 nums[start] 移除记录
hash.remove(nums[start])
# 窗口左端向右移动
start += 1
# 此时，滑动窗口可以接纳 nums[end]
hash.add(nums[end])
# 维护变量 sum
sums += nums[end]
# 维护变量 largest
largest = max(largest,sums)
# 【5、返回所需要的答案】
return largest
# 题目：LC1695. 删除子数组的最大得分
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：不定滑窗
# 代码看不懂的地方，请直接在群上提问
# 本质上是求【不含重复元素的子数组的最大和】
# 故用哈希集合set()维护滑窗过程
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
ans, left = 0, 0
windows_sum = 0
hash_set = set()
for right, num in enumerate(nums):
# A1
# num的值加入windows_sum中
windows_sum += num
# A2
# 如果num位于哈希集合中，left右移
while(num in hash_set):
windows_sum -= nums[left]
hash_set.remove(nums[left])
left += 1
# A3
# while外部num一定不位于哈希集合，即窗口中一定无重复数字
# 此时可以更新答案
ans = max(ans, windows_sum)
# A1
# num需要加入哈希集合中
hash_set.add(num)
return ans
四、复杂度分析
时间复杂度：O(N)