3487. 删除后的最大子数组元素和
题目描述
给你一个整数数组 nums 。
你可以从数组 nums 中删除任意数量的元素，但不能将其变为 空 数组。执行删除操作后，选出 nums 中满足下述条件的一个子数组：
- 子数组中的所有元素 互不相同 。
- 最大化 子数组的元素和。
返回子数组的 最大元素和 。
子数组 是数组的一个连续、非空 的元素序列。
示例 1：
输入：nums = [1,2,3,4,5]
输出：15
解释：
不删除任何元素，选中整个数组得到最大元素和。
示例 2：
输入：nums = [1,1,0,1,1]
输出：1
解释：
删除元素 nums[0] == 1、nums[1] == 1、nums[2] == 0 和 nums[3] == 1 。选中整个数组 [1] 得到最大元素和。
示例 3：
输入：nums = [1,2,-1,-2,1,0,-1]
输出：3
解释：
删除元素 nums[2] == -1 和 nums[3] == -2 ，从 [1, 2, 1, 0, -1] 中选中子数组 [2, 1] 以获得最大元素和。
提示：
1 <= nums.length <= 100-100 <= nums[i] <= 100
解法
方法一：贪心 + 哈希表
我们先找出数组中的最大值 $\textit{mx}$，如果 $\textit{mx} \leq 0$，那么数组中所有元素都小于等于 $0$，由于需要选出一个元素和最大的非空子数组，那么最大元素和就是 $\textit{mx}$。
如果 $\textit{mx} > 0$，那么我们需要找出数组中所有不同的正整数，并且这些正整数的和最大。我们可以使用一个哈希表 $\textit{s}$ 来记录所有不同的正整数，然后遍历数组，将所有不同的正整数加起来即可。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。
Python3
class Solution:
def maxSum(self, nums: List[int]) -> int:
mx = max(nums)
if mx <= 0:
return mx
ans = 0
s = set()
for x in nums:
if x < 0 or x in s:
continue
ans += x
s.add(x)
return ans
Java
class Solution {
public int maxSum(int[] nums) {
int mx = Arrays.stream(nums).max().getAsInt();
if (mx <= 0) {
return mx;
}
boolean[] s = new boolean[201];
int ans = 0;
for (int x : nums) {
if (x < 0 || s[x]) {
continue;
}
ans += x;
s[x] = true;
}
return ans;
}
}
C++
class Solution {
public:
int maxSum(vector<int>& nums) {
int mx = ranges::max(nums);
if (mx <= 0) {
return mx;
}
unordered_set<int> s;
int ans = 0;
for (int x : nums) {
if (x < 0 || s.contains(x)) {
continue;
}
ans += x;
s.insert(x);
}
return ans;
}
};
Go
func maxSum(nums []int) (ans int) {
mx := slices.Max(nums)
if mx <= 0 {
return mx
}
s := make(map[int]bool)
for _, x := range nums {
if x < 0 || s[x] {
continue
}
ans += x
s[x] = true
}
return
}
TypeScript
function maxSum(nums: number[]): number {
const mx = Math.max(...nums);
if (mx <= 0) {
return mx;
}
const s = new Set<number>();
let ans: number = 0;
for (const x of nums) {
if (x < 0 || s.has(x)) {
continue;
}
ans += x;
s.add(x);
}
return ans;
}