1695-删除子数组的最大得分

给你一个正整数数组 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 <= 105
• 1 <= nums[i] <= 104

Problem: 1695. 删除子数组的最大得分

[TOC]

思路

本题要求的是最大的不出现重复元素的子数组之和。
常见思路为滑动窗口+哈希表。优化的关键在于出现重复元素时，如何快速滑动左窗口并且更新子数组之和。

解题方法

为方便描述，称新元素与滑动窗口的旧元素相同时，发生了“冲突”。
定义特殊的前缀数组presums：presums[num]表示以新元素num结尾的nums数组前缀和，初始时均为0
使用conflictSum记录发生冲突时，旧元素对应的presums值。
定义presum为遍历数组时的前缀和。
res为要求的最大的无冲突子数组之和。

算法过程

遍历数组元素num：
若conflictSum<presums[num],说明当前窗口num重复出现，需要滑动左窗口，把conflictSum置为presums[num]即可。否则，左窗口无需滑动。
无论左窗口是否滑动，右窗口都需要向右滑动一步，并更新presums[num]。
此时的窗口对应一个合法的子数组，其和为presum-conflictSum,以此更新最终结果res。

优化细节

注意到最终结果res不需要每次都更新。发生冲突时，presum-conflictSum恰好对应一个完整的子数组。由于题目限制数组元素非负，可以在此处更新res。最后一个完整的子数组需要单独更新一遍res。

复杂度

• 时间复杂度:

  O(n)

• 空间复杂度:

  O(C),C为数组元素取值范围。

Code

[]

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        res=0
        conflictSum=0
        presums=[0]*10001
        ##记录最新的以num结尾的数组前缀和
        presum=0
        for num in nums:
            if conflictSum<presums[num]:
                res=max(res,presum-conflictSum)
                conflictSum=presums[num]
            presum+=num
            presums[num]=presum
            # res=max(res,presum-conflictSum)
        res=max(res,presum-conflictSum)
        return res