删除子数组的最大得分 图解题解
这道题到底在问什么
- 输入
- nums = [4,2,4,5,6]
- 输出
- 17（取 [4,5,6]，和最大且无重复）
最优解：一步一步想明白
- 3两件事记牢：窗口内永远无重复；sum 随纳入加、随吐出减，每纳入一个新数就用 sum 刷新 best。下面一步步演给你看。
- 4开始前：窗口是空的，窗口和 sum=0，历史最大 best=0。左右指针都还没出发。
- 5右指针 r 走到下标 0，值是 2。这个值在窗口里没出现过，直接纳入。
- 6把下标 0（值 2）纳入窗口，窗口和增加到 2。用它刷新历史最大，best = 2。
- 7右指针 r 走到下标 1，值是 1。这个值在窗口里没出现过，直接纳入。
- 8把下标 1（值 1）纳入窗口，窗口和增加到 3。用它刷新历史最大，best = 3。
- 9右指针 r 走到下标 2，值是 5。这个值在窗口里没出现过，直接纳入。
- 10把下标 2（值 5）纳入窗口，窗口和增加到 8。用它刷新历史最大，best = 8。
- 11右指针 r 走到下标 3，值是 3。这个值在窗口里没出现过，直接纳入。
- 12把下标 3（值 3）纳入窗口，窗口和增加到 11。用它刷新历史最大，best = 11。
- 13右指针 r 走到下标 4，值是 2。这个值已在当前窗口里，先从左边吐数把它清掉。
- 14从左端吐出下标 0（值 2，标红），窗口和减去它变成 9，左指针右移到 1。重复已清除。
- 15把下标 4（值 2）纳入窗口，窗口和增加到 11。用它刷新历史最大，best = 11。
- 16右指针 r 走到下标 5，值是 6。这个值在窗口里没出现过，直接纳入。
- 17把下标 5（值 6）纳入窗口，窗口和增加到 17。用它刷新历史最大，best = 17。
- 18右指针 r 走到下标 6，值是 1。这个值已在当前窗口里，先从左边吐数把它清掉。
- 19从左端吐出下标 1（值 1，标红），窗口和减去它变成 16，左指针右移到 2。重复已清除。
- 20把下标 6（值 1）纳入窗口，窗口和增加到 17。用它刷新历史最大，best = 17。
- 21右指针 r 走到下标 7，值是 4。这个值在窗口里没出现过，直接纳入。
- 22把下标 7（值 4）纳入窗口，窗口和增加到 21。用它刷新历史最大，best = 21。
- 23右指针 r 走到下标 8，值是 3。这个值已在当前窗口里，先从左边吐数把它清掉。
- 24从左端吐出下标 2（值 5，标红），窗口和减去它变成 16，左指针右移到 3。还有重复，继续吐。
- 25从左端吐出下标 3（值 3，标红），窗口和减去它变成 13，左指针右移到 4。重复已清除。
- 26把下标 8（值 3）纳入窗口，窗口和增加到 16。用它刷新历史最大，best = 21。
- 27扫描结束。所有无重复窗口里，和最大的就是高亮的这一段，best=21 就是最终答案。
⚠️ 容易写错的地方
✗ 错：吐出左端时只移指针、忘了从 sum 里减掉它
✓ 对：l 右移的同时 sum 减去被吐出的值
sum 必须始终等于当前窗口内的和，漏减会让 sum 偏大、best 算错
✗ 错：用 while 而不是 if 来收缩，或反过来
✓ 对：必须用 while 一直吐到重复消失为止
一次纳入可能要吐掉多个左端数，if 只吐一次会留着重复，窗口仍不合法
✗ 错：先纳入新数再判重复
✓ 对：先把重复吐干净，再纳入新数
顺序反了会把重复值先加进集合，while 条件立刻失效，窗口里残留重复
完整代码（Python / C++ / Java）
Python
def maximumUniqueSubarray(nums):
seen = set() # 窗口内已有的数
l = cur = best = 0 # 左指针 / 窗口和 / 答案
for r in range(len(nums)):
while nums[r] in seen: # 撞重复 → 从左边吐
seen.remove(nums[l])
cur -= nums[l]
l += 1
seen.add(nums[r]) # 纳入新数
cur += nums[r]
best = max(best, cur) # 刷新答案
return bestC++
int maximumUniqueSubarray(vector<int>& nums){
unordered_set<int> seen;
int l = 0, cur = 0, best = 0;
for (int r = 0; r < nums.size(); r++) {
while (seen.count(nums[r])) {
seen.erase(nums[l]); cur -= nums[l]; l++;
}
seen.insert(nums[r]); cur += nums[r];
best = max(best, cur);
}
return best;
}Java
public int maximumUniqueSubarray(int[] nums) {
Set<Integer> seen = new HashSet<>();
int l = 0, cur = 0, best = 0;
for (int r = 0; r < nums.length; r++) {
while (seen.contains(nums[r])) {
seen.remove(nums[l]); cur -= nums[l]; l++;
}
seen.add(nums[r]); cur += nums[r];
best = Math.max(best, cur);
}
return best;
}复杂度
时间
O(n)
左右指针各自只从头走到尾一次，每个元素最多被纳入和吐出各一次
空间
O(n)
用一个集合记录窗口内出现过的数，最坏装下整个数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 删除子数组的最大得分 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
sum 和 best 分别代表什么？+
sum 是当前窗口（无重复那段）里所有数的和，会随纳入加、随吐出减；best 是历史上见过的最大窗口和，只增不减。答案是 best。
为什么这题不用先排序或枚举所有子数组？+
元素都是正整数，窗口越长和越大，所以只需让窗口在「无重复」约束下尽量长。双指针线性扫一遍即可，O(n) 远优于枚举的 O(n²)。
如果数组里全是同一个数，结果是多少？+
返回那个数本身。每次纳入新值都和窗口里的重复，会立刻被吐成只剩一个元素的窗口，最大和就是单个元素。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 删除子数组的最大得分 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。