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

题目链接3487. 删除后的最大子数组元素和 - 力扣LeetCode题目描述给你一个整数数组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]得到最大元素和。解题思路问题理解题目要求计算数组中所有不重复的非负数的和。如果数组中全是负数则返回最大的负数。核心思路使用一个HashSet来记录已经处理过的非负数确保每个非负数只被累加一次。遍历数组对每个元素进行分类处理如果是负数更新当前最大的负数。如果是非负数且未被处理过即set.add(x)返回true则将其累加到sum中。最后检查set是否为空如果为空说明数组中没有非负数返回最大的负数。否则返回非负数的累加和。关键点利用HashSet的去重特性确保非负数只被累加一次。通过mx变量动态维护最大的负数以处理全为负数的情况。题解代码classSolution{publicintmaxSum(int[]nums){// 使用HashSet来记录已经处理过的非负数SetIntegersetnewHashSet();// sum用于累加所有不重复的非负数intsum0;// mx用于记录最大的负数如果所有数都是负数时使用intmxInteger.MIN_VALUE;// 遍历数组中的每个元素for(intx:nums){if(x0){// 如果是负数更新最大的负数mxMath.max(mx,x);}elseif(set.add(x)){// 如果是非负数且未被处理过set.add(x)返回true表示成功添加// 则将其加入sumsumx;}}// 如果set为空说明所有数都是负数返回最大的负数// 否则返回非负数的和returnset.isEmpty()?mx:sum;}}复杂度分析时间复杂度遍历数组的时间复杂度为O(n)其中n是数组的长度。HashSet的插入操作set.add(x)的平均时间复杂度为O(1)。因此总的时间复杂度为O(n)。空间复杂度HashSet在最坏情况下需要存储所有非负数因此空间复杂度为O(n)例如所有数都是非负数且不重复时。其他变量如sum、mx占用常数空间可以忽略。