欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。
@[toc]
题目描述
[1695] 删除子数组的最大得分
给你一个正整数数组 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
Related Topics
题目剖析&信息挖掘
此题与
最长不重复子串类似，可以使用双指针哈希法。
解题思路
方法一 双指针哈希法
思路
- 设置2个指针i, j分别表示当前选中序列中的头和尾，sum为 i到j数字合。
- j不停往前走（sum加上相应的数字），判断i, j中是不是有重复
- 如果重复肯定是nums[j]重复，把i往前移(sum减去相应的数字)。
- 取所有sum中最大值即为答案
- i, j最多移动n次，复杂O(n)
注意
- i 始终<= j
- sum 要相应同步
知识点
- 双指针
- 哈希
- 数组
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
参考
代码实现
func maximumUniqueSubarray(nums []int) int {
m := make(map[int]int, 1000)
sum :=0
maxSum :=0
for i,j:=0,0;j<len(nums);j++ {
m[nums[j]]++
sum += nums[j]
for ;i<j && m[nums[j]]>1 ; i++ {
sum -= nums[i]
m[nums[i]]--
}
if sum>maxSum {
maxSum = sum
}
}
return maxSum
}
相关题目
最长不重复子串
本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。
