LeetCode 题解工作台
删除后的最大子数组元素和
给你一个整数数组 nums 。 你可以从数组 nums 中删除任意数量的元素，但不能将其变为 空 数组。执行删除操作后，选出 nums 中满足下述条件的一个子数组： 子数组中的所有元素 互不相同 。 最大化 子数组的元素和。 返回子数组的 最大元素和 。 子数组 是数组的一个连续、 非空 的元素序列…
3
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们先找出数组中的最大值 ，如果 $\textit{mx} \leq 0$，那么数组中所有元素都小于等于 ，由于需要选出一个元素和最大的非空子数组，那么最大元素和就是 。 如果 $\textit{mx} > 0$，那么我们需要找出数组中所有不同的正整数，并且这些正整数的和最大。我们可以使用一个哈希表 来记录所有不同的正整数，然后遍历数组，将所有不同的正整数加起来即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 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
解题思路
方法一：贪心 + 哈希表
我们先找出数组中的最大值 ，如果 ，那么数组中所有元素都小于等于 ，由于需要选出一个元素和最大的非空子数组，那么最大元素和就是 。
如果 ，那么我们需要找出数组中所有不同的正整数，并且这些正整数的和最大。我们可以使用一个哈希表 来记录所有不同的正整数，然后遍历数组，将所有不同的正整数加起来即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
The candidate should identify the importance of handling duplicates efficiently with a hash table.
- question_mark
A strong answer will demonstrate how to apply a sliding window and adjust the sum dynamically.
- question_mark
Watch for understanding of edge cases like arrays with all negative elements or arrays with only duplicates.
常见陷阱
外企场景- error
Failing to handle edge cases like arrays with only one element or all elements being the same.
- error
Not optimizing for space by relying too heavily on brute-force methods to check for uniqueness.
- error
Overcomplicating the problem by trying to delete elements arbitrarily instead of using efficient window adjustments.
进阶变体
外企场景- arrow_right_alt
Change the deletion rule, allowing only one deletion per subarray.
- arrow_right_alt
Introduce additional constraints, such as a minimum subarray size.
- arrow_right_alt
Allow a fixed number of deletions and find the maximum sum after performing those deletions.