题目
给你一个整数数组 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
解题思路
题目描述：
- 可以从数组
nums中删除任意数量的元素。 - 删除后，剩下的数组不能是空数组。
- 从剩下的数组中，选出一个连续的子数组。
- 这个子数组必须满足所有元素互不相同。
- 目标是最大化这个子数组的元素和。
因为我们可以任意删除元素，这意味着我们可以让任何我们想要保留的元素（只要它们在原数组中存在）在剩下的数组中变成连续的。基于这个思路，我们只需要从 nums 数组里挑选出一组不重复的数，让它们的和最大。
如何让一堆数的和最大呢？策略非常直观：
- 所有正数都应该被选中。因为加上一个正数总会使和变大。
- 所有负数都不应该被选中（除非万不得已）。因为加上一个负数总会使和变小。
- 0 可选可不选，它对总和没有影响。
基于这个策略，我们可以分两种情况来讨论：
情况一：数组中存在唯一的正数
- 首先，找出
nums数组中所有不重复的数字。使用一个集合（Set / HashSet）是实现这一步的最好方法。 - 然后，遍历这些不重复的数字，把其中所有大于零的数加起来。
- 这个和就是我们能得到的最大和。因为我们选取了所有能使总和增加的元素（所有唯一的正数），并且避开了所有会使总和减少的元素（所有唯一的负数）。由于至少有一个正数，所以这个和必然大于0，也满足了“数组不能为空”的条件。
示例分析 ([1, 2, -1, -2, 1, 0, -1])
- 唯一元素集合：
{1, 2, -1, -2, 0} - 其中的正数是：
1和2。 - 最大和 =
1 + 2 = 3。这与示例输出一致。
情况二：数组中不存在唯一的正数
如果 nums 中所有的唯一数都是 0 或者负数呢？
- 按照情况一的逻辑，我们会把所有正数加起来，但因为没有正数，所以和为 0。
- 但是题目要求最终选出的子数组不能为空。这意味着我们必须至少选择一个元素。
- 在这种所有数都
<= 0的情况下，为了让和最大，我们应该选择那个“最大”的数（也就是最不负的那个数，或者 0）。
代码
class Solution {
public:
int maxSum(vector<int>& nums) {
// 哈希数组，用于记录正数是否已出现过，以实现去重
bool is_seen[101] = {false};
// 记录所有不重复正数的和
long long positive_sum = 0;
// 记录整个数组中的最大值，用于处理全是负数的边界情况
int largest_num = -101; // 任何小于-100的数都可以作为初始值
for(int num : nums)
{
// 实时更新数组中的最大值
if(num > largest_num) {
largest_num = num;
}
// 如果当前数字是正数，并且是第一次出现
if(num > 0 && !is_seen[num]) {
positive_sum += num;
is_seen[num] = true; // 标记为已出现
}
}
// 最终决策：
// 如果连最大的数都是负数，说明没有正数可选，按题意只能选择最大的那个负数。
if(largest_num < 0) {
return largest_num;
}
// 否则（即数组中存在正数或0），最大和就是所有不重复正数的和。
return positive_sum;
}
};
主要使用了哈希表进行优化。
复杂度分析
- 时间复杂度：O(N) 因为代码只完整地遍历了一遍输入数组。
- 空间复杂度：O(1) 因为额外创建的数组大小是固定的，不随输入规模变化。