LeetCode 1695. 删除子数组的最大得分
题目描述
题意分析
从正整数数组中选择一个连续子数组，要求其中所有元素的值互不相同，删除它得到的分数就是这些元素的和。只删除这一段，求可以获得的最大分数。
需要最大化的是和，不是长度；连续性又要求不能在遇到重复值后只随意移除中间某个元素，再把两边拼成候选。元素全部为正数，是后面用最长合法窗口代表当前右端最佳得分的关键条件。
解法：无重复滑动窗口与窗口和
核心思路
[!blue]
用集合保存当前窗口中出现的值，
left表示窗口起点，sum保存窗口元素和。每次处理新值之前，旧窗口都已经没有重复，因此集合足以表示窗口成员，不需要为窗口内部再记录重复频次。如果新值还不在集合中，可以直接加入窗口；如果已经存在，就必须让左边界越过旧的那一次出现。代码从左到右依次移出元素，同时从集合删除并从
sum减去对应值，直到集合不再含有新值，再把新值加入。这些同步操作始终维持集合、边界与窗口和描述的是同一个连续区间。收缩只进行到刚好消除重复的位置，因此得到的是以当前元素为右端的最长无重复窗口。被排除的更早起点会包含重复的两次出现，之后右端继续扩大也无法使它们重新合法，所以左边界不需要回退。
为什么只考察这个最长窗口就能求最大和？对于同一个右端，任何更短的合法窗口都是它的后缀；数组元素全部为正，删除前面的一部分只会降低元素和。因此当前最长合法窗口也就是当前右端的最高得分窗口。
处理每个右端后，用窗口和更新全局答案，就覆盖了所有可能的最优区间。无需真的从输入数组删除元素，只需移动边界并维护状态即可。
解题步骤
- 初始化空集合、左边界零、窗口和零、答案零。
- 依次处理数组中的新值；只要集合已含该值，就移出当前左端，更新集合与窗口和，再推进左边界。
- 重复消失后，将新值加入集合和窗口和。
- 用当前窗口和更新最大分数，全部处理后返回答案。
代码实现
class Solution {
public int maximumUniqueSubarray(int[] nums) {
Set<Integer> window = new HashSet<>();
int left = 0;
int sum = 0;
int answer = 0;
for (int value : nums) {
while (window.contains(value)) {
sum -= nums[left];
window.remove(nums[left++]);
}
window.add(value);
sum += value;
answer = Math.max(answer, sum);
}
return answer;
}
}
func maximumUniqueSubarray(nums []int) int {
window := map[int]bool{}
left, sum, answer := 0, 0, 0
for _, value := range nums {
for window[value] {
sum -= nums[left]
delete(window, nums[left])
left++
}
window[value] = true
sum += value
answer = max(answer, sum)
}
return answer
}
复杂度分析
- 时间复杂度：期望 $O(n)$。每个元素只进入窗口一次，也最多离开一次，哈希集合操作期望为常量时间。
- 空间复杂度：$O(n)$ 上界，保存当前无重复窗口的值；其余边界和累计量只需常量空间。
关键点总结
[!green]
- 去重条件决定何时必须收缩，正数条件保证合法窗口尽量长时得分也最大。
- 旧窗口已经唯一，新重复只可能由当前新值引入，收缩到旧副本离开即可。
- 移出时同时更新集合、窗口和及左边界，加入完成后才更新答案。
易错点总结
[!yellow]
- 遇到重复只移动一次左端，旧副本可能还留在窗口中，应持续收缩到重复消失。
- 只从集合删除重复值，却不移除它之前的元素，会让记录不再对应连续子数组。
- 移出元素时忘记从
sum减去，答案会混入已经离开窗口的分数。- 把窗口长度当成得分返回，忽略不同正整数的数值大小。
- 将同样结论直接用于含负数数组，最长合法窗口未必有最大和，正数前提不能省略。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 3. 无重复字符的最长子串 | 中等 | 相同的去重窗口，本题维护元素和，原题维护长度；正数条件使最长窗口同时拥有最大和。 |
| 209. 长度最小的子数组 | 中等 | 同样维护正数窗口和，但原题在达到下界时收缩求最短，本题因重复才收缩求最大和。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！