Easy

题目描述

给你一个整数数组 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

提示：

  • 如果数组中的最大元素小于零，答案是最大元素
  • 否则，答案是所有大于等于零的唯一值的和

解题思路

这道题要求我们在删除一些元素后，找到一个具有唯一元素的子数组，使其和最大。

核心观察：

  1. 我们可以删除任意元素，所以实际上是要找出所有数值中最优的组合
  2. 子数组要求元素唯一，意味着相同的值最多只能选择一个
  3. 既然可以删除元素，我们应该保留每个数值的最大值（如果有重复）

解题思路：

方法一：哈希表统计

  • 使用哈希表记录每个数值出现的最大值
  • 遍历数组，对于每个数值，只保留其最大的出现值
  • 最后将所有正数相加，如果结果为0或负数，则返回数组中的最大值

方法二：直接处理（推荐） 根据题目提示，我们可以直接分析：

  • 如果数组最大值 < 0，答案就是最大值
  • 否则，答案是所有大于等于0的唯一值的和

具体步骤：

  1. 使用集合去重，得到所有唯一值
  2. 找出最大值
  3. 如果最大值 < 0，返回最大值
  4. 否则，返回所有非负唯一值的和

这种方法简洁高效，时间复杂度为 O(n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    int maxSum(vector<int>& nums) {
        unordered_set<int> unique_nums(nums.begin(), nums.end());
        
        int max_val = *max_element(nums.begin(), nums.end());
        
        if (max_val < 0) {
            return max_val;
        }
        
        int sum = 0;
        for (int num : unique_nums) {
            if (num >= 0) {
                sum += num;
            }
        }
        
        return sum;
    }
};

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        unique_nums = set(nums)
        max_val = max(nums)
        
        if max_val < 0:
            return max_val
        
        return sum(num for num in unique_nums if num >= 0)

public class Solution {
    public int MaxSum(int[] nums) {
        var uniqueNums = new HashSet<int>(nums);
        int maxVal = nums.Max();
        
        if (maxVal < 0) {
            return maxVal;
        }
        
        return uniqueNums.Where(num => num >= 0).Sum();
    }
}

var maxSum = function(nums) {
    const uniqueNums = new Set(nums);
    const maxVal = Math.max(...nums);
    
    if (maxVal < 0) {
        return maxVal;
    }
    
    let sum = 0;
    for (const num of uniqueNums) {
        if (num >= 0) {
            sum += num;
        }
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
时间复杂度O(n)O(n)
空间复杂度O(n)O(n)
  • 时间复杂度：O(n)，需要遍历数组一次来创建集合，再遍历集合一次来计算和
  • 空间复杂度：O(n)，使用哈希集合存储唯一元素，最坏情况下所有元素都不同

相关题目