What is the main strategy for solving Maximum Erasure Value?

The primary strategy is using a sliding window and a hash map to ensure the subarray contains unique elements while maximizing the sum.

How do I handle duplicates in the array for this problem?

Duplicates can be handled by adjusting the left pointer of the sliding window whenever a duplicate is encountered, ensuring uniqueness of the subarray.

Can this problem be solved with a brute force approach?

While a brute force approach is possible, it would be inefficient with a time complexity of O(n^2). A sliding window approach with a hash map is much more optimal.

What is the time complexity of the optimal solution for this problem?

The optimal solution has a time complexity of O(n) because each element is processed once, and hash lookups take constant time.

What would be the space complexity for this problem?

The space complexity is O(n) due to the hash map used to store the last seen positions of elements in the array.

#1695

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

删除子数组的最大得分

给你一个正整数数组 nums ，请你从中删除一个含有若干不同元素的子数组。删除子数组的得分就是子数组各元素之和。返回只删除一个子数组可获得的最大得分。如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一…

数组哈希表滑动窗口

题目描述

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的得分就是子数组各元素之和。

返回 只删除一个 子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]

示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

lightbulb

解题思路

方法一：数组或哈希表 + 前缀和

我们用数组或哈希表 $\text{d}$ 记录每个数字最后一次出现的位置，用前缀和数组 $\text{s}$ 记录从起点到当前位置的和。我们用变量 $j$ 记录当前不重复子数组的左端点。

遍历数组，对于每个数字 $v$ ，如果 $\text{d}[v]$ 存在，那么我们更新 $j$ 为 $\max(j, \text{d}[v])$ ，这样就保证了当前不重复子数组不包含 $v$ 。然后我们更新答案为 $\max(\text{ans}, \text{s}[i] - \text{s}[j])$ ，最后更新 $\text{d}[v]$ 为 $i$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\text{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        d = [0] * (max(nums) + 1)
        s = list(accumulate(nums, initial=0))
        ans = j = 0
        for i, v in enumerate(nums, 1):
            j = max(j, d[v])
            ans = max(ans, s[i] - s[j])
            d[v] = i
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate implement a sliding window efficiently with hash lookups?
question_mark
Does the candidate demonstrate the ability to optimize space and time complexity using hash maps?
question_mark
How well does the candidate handle edge cases like arrays with minimal or repetitive values?

warning

常见陷阱

外企场景

error
Failing to handle duplicate values correctly when adjusting the window.
error
Not updating the sum efficiently after modifying the sliding window.
error
Overcomplicating the solution with unnecessary nested loops or extra space.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array contains only one element?
arrow_right_alt
How would the solution change if the elements in the array were sorted?
arrow_right_alt
What if the problem required finding the maximum product instead of the sum?

help

常见问题

外企场景

继续练习

#1658 将 x 减到 0 的最小操作数 #1477 找两个和为目标值且不重叠的子数组 #2009 使数组连续的最少操作数