1695. 删除子数组的最大得分Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个正整数数组 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 <= 105
- 1 <= nums[i] <= 104
# 思路
滑动窗口
# 解法
class Solution {
public int maximumUniqueSubarray(int[] nums) {
int ans = 0;
int sum = 0;
int left = 0;
int []cut = new int[100000];
for (int i : nums){
sum += i;
cut[i] += 1; // 更新当前元素出现次数
while (cut[i] > 1){
int num = nums[left];
cut[num] -= 1;
sum -= num;
left++;
}
ans = Math.max(ans, sum);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 总结
- 分析出几种情况，然后分别对各个情况实现
