3487. 删除后的最大子数组元素和

题目链接

3487. 删除后的最大子数组元素和 - 力扣（LeetCode）

题目描述

给你一个整数数组nums。

你可以从数组nums中删除任意数量的元素，但不能将其变为 空 数组。执行删除操作后，选出nums中满足下述条件的一个子数组：

1. 子数组中的所有元素 互不相同 。
2. 最大化 子数组的元素和。

返回子数组的 最大元素和 。

子数组 是数组的一个连续、非空 的元素序列。

题目示例

示例 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]得到最大元素和。

解题思路

1. 问题理解：题目要求计算数组中所有不重复的非负数的和。如果数组中全是负数，则返回最大的负数。
2. 核心思路：
   • 使用一个HashSet来记录已经处理过的非负数，确保每个非负数只被累加一次。
   • 遍历数组，对每个元素进行分类处理：
     • 如果是负数，更新当前最大的负数。
     • 如果是非负数且未被处理过（即set.add(x)返回true），则将其累加到sum中。
   • 最后检查set是否为空：
     • 如果为空，说明数组中没有非负数，返回最大的负数。
     • 否则，返回非负数的累加和。
3. 关键点：
   • 利用HashSet的去重特性确保非负数只被累加一次。
   • 通过mx变量动态维护最大的负数，以处理全为负数的情况。

题解代码

classSolution{publicintmaxSum(int[]nums){// 使用HashSet来记录已经处理过的非负数Set<Integer>set=newHashSet<>();// sum用于累加所有不重复的非负数intsum=0;// mx用于记录最大的负数（如果所有数都是负数时使用）intmx=Integer.MIN_VALUE;// 遍历数组中的每个元素for(intx:nums){if(x<0){// 如果是负数，更新最大的负数mx=Math.max(mx,x);}elseif(set.add(x)){// 如果是非负数且未被处理过（set.add(x)返回true表示成功添加）// 则将其加入sumsum+=x;}}// 如果set为空（说明所有数都是负数），返回最大的负数// 否则返回非负数的和returnset.isEmpty()?mx:sum;}}

复杂度分析

1. 时间复杂度：
   • 遍历数组的时间复杂度为O(n)，其中n是数组的长度。
   • HashSet的插入操作set.add(x)的平均时间复杂度为O(1)。
   • 因此，总的时间复杂度为O(n)。
2. 空间复杂度：
   • HashSet在最坏情况下需要存储所有非负数，因此空间复杂度为O(n)（例如所有数都是非负数且不重复时）。
   • 其他变量（如sum、mx）占用常数空间，可以忽略。