给你一个正整数数组 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]
思路:
我们创建两个指针来标记移动,left,right,一开始初始化为0,然后right指针开始移动,sum用来加和,每加一个值,就要判断是否重复,可以用set集合,然后用set.contaions判断,当重复之后,就要从left开始遍历比如下面:
public static int a(int[] nums){
int left=0;
int right=0;
int sum=0;
int maxend=0;
//存储为了判断是否含有相同的值
HashSet<Integer> set =new HashSet<>();
for(int i=0;i<nums.length;i++) {
while(set.contains(nums[i])){
sum -=nums[left];
set.remove(nums[left]);
left++;
}
set.add(nums[i]);
sum +=nums[i];
right++;
maxend=max(sum,maxend);
}
return maxend;
}