难度: Medium
给你一个正整数数组 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 <= 1051 <= nums[i] <= 104运行时间: 201 ms
内存: 27.3 MB
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
# 1) 求前缀和
pre_num = [0]
for num in nums:
pre_num.append(pre_num[-1] + num)
# 2) 使用字典记录标号, 快速确定滑动窗口开始位置
start, pos_dict, ans = 0, {}, 0
for i, n in enumerate(nums):
if n in pos_dict and pos_dict[n] >= start:
ans = max(ans, pre_num[i] - pre_num[start])
start = pos_dict[n] + 1
pos_dict[n] = i
# 3) 边界处理
return max(ans, pre_num[-1] - pre_num[start])
此题解采用滑动窗口加上哈希表的方法来解决问题。首先通过计算前缀和数组来快速求出任何子数组的和。然后，使用一个哈希表来记录每个元素最后出现的位置。通过遍历数组，利用哈希表来判断当前元素是否已在当前考虑的子数组中出现过。如果出现过，说明当前子数组中已包含重复元素，需要调整滑动窗口的起始位置到重复元素的下一个位置。每次调整后，计算并更新可能的最大子数组和。最后，需要处理边界情况，即当数组遍历完成后，检查最后一个可能的子数组的得分。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
# 1) 计算前缀和用于快速获取子数组和
pre_num = [0]
for num in nums:
pre_num.append(pre_num[-1] + num)
# 2) 使用哈希表记录元素最后出现的位置，用于调整滑动窗口
start, pos_dict, ans = 0, {}, 0
for i, n in enumerate(nums):
if n in pos_dict and pos_dict[n] >= start:
ans = max(ans, pre_num[i] - pre_num[start])
start = pos_dict[n] + 1
pos_dict[n] = i
# 3) 处理遍历结束后的最后一个窗口
return max(ans, pre_num[-1] - pre_num[start])
前缀和数组是一种高效计算子数组和的方法。通过构造一个数组，其中每个元素表示从数组开始到当前位置的元素总和，可以快速计算任意子数组的和。具体来说，子数组从索引i到j的和可以通过pre_num[j+1] - pre_num[i]来得到，这样只需要O(1)的时间复杂度，大大提高了效率，尤其是在需要频繁计算子数组和的情况下非常有用。
在滑动窗口算法中，哈希表用于记录每个元素最后一次出现的位置。当遍历到数组中的某个元素时，可以快速检查该元素是否已经在当前考虑的子数组中出现过。如果已出现，并且出现的位置在当前滑动窗口的起始位置之后，这表明需要调整窗口以排除重复元素。这时，滑动窗口的起始位置更新为该重复元素上一次出现位置的下一个位置，从而保证窗口中的元素都是唯一的。
如果当前元素在哈希表中的记录位置小于滑动窗口的起始位置，这意味着这个记录的位置已不在当前考虑的子数组中。因此，这种情况下无需调整滑动窗口的起始位置，可以直接更新哈希表中该元素的位置为当前索引，继续向前遍历数组。这样做确保了哈希表总是反映每个元素最近的位置，而不会错误地引起不必要的窗口调整。
每次当检测到当前元素已存在于当前子数组中时，算法会将滑动窗口的起始位置调整到该重复元素上次出现位置的下一个位置。这种调整方式确保了所有在新起始位置之前的元素都不会包含在新的窗口中，从而移除了重复元素。通过这种方法，每次调整后的滑动窗口都只包含唯一的元素，保证了子数组的独特性。