class Solution {
public:
int maximumUniqueSubarray(vector<int>& nums) {
}
};
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 <= 1051 <= nums[i] <= 104原站题解
python3 解法, 执行用时: 364 ms, 内存消耗: 25.9 MB, 提交时间: 2023-03-10 09:39:56
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
n = len(nums)
visited = set()
res = 0
l, r = 0, 0
_sum = 0
while r < n:
while l < r and nums[r] in visited:
_sum -= nums[l]
visited.remove(nums[l])
l += 1
visited.add(nums[r])
_sum += nums[r]
res = max(res, _sum)
r += 1
return res
python3 解法, 执行用时: 8868 ms, 内存消耗: 25.8 MB, 提交时间: 2023-03-10 09:39:14
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
start, poiDict, ans = 0, {}, 0
for i, c in enumerate(nums):
if c in poiDict and poiDict[c] >= start:
ans = max(ans, sum(list(nums[start : i])))
start = poiDict[c] + 1
poiDict[c] = i
return max(ans, sum(nums[start : len(nums)]))
java 解法, 执行用时: 99 ms, 内存消耗: 55.8 MB, 提交时间: 2023-03-10 09:38:19
class Solution {
public int maximumUniqueSubarray(int[] nums) {
//1.建窗口
Map<Integer, Integer> window = new HashMap<>();
int left = 0, right = 0;
int res = 0, cur = 0;
while (right < nums.length) {
//2.右侧扩张
int k = nums[right++];
window.put(k, window.getOrDefault(k, 0) + 1);
cur += k;
//3.判断是否要左侧收缩
while (window.get(k) > 1){
int d = nums[left++];
window.put(d, window.get(d) - 1);
cur -= d;
}
res = Math.max(res, cur);
}
return res;
}
}
java 解法, 执行用时: 52 ms, 内存消耗: 53.5 MB, 提交时间: 2023-03-10 09:36:32
class Solution {
public int maximumUniqueSubarray(int[] nums) {
Set<Integer> set = new HashSet<>();
int max = 0, sum = 0, start = 0;
for (int i = 0; i < nums.length; i++) {
while (!set.isEmpty() && set.contains(nums[i])) {
sum -= nums[start];
set.remove(nums[start]);
start++;
}
set.add(nums[i]);
sum += nums[i];
max = Math.max(sum, max);
}
return max;
}
}