题目

给你一个正整数数组 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^5
1 <= nums[i] <= 10^4

思路

使用 滑动窗口。窗口的左右边界由两个指针 left 和 right 来定义。

right 指针：负责向右探索，扩大窗口。
left 指针：当窗口内出现重复元素时，负责向右收缩窗口，以重新满足“元素唯一”的条件。

所有需要的变量：

left, right: 窗口的左右边界指针，初始都为 0。
max_score: 用于记录全局的最大得分，初始为 0。
current_sum: 用于记录当前窗口内所有元素的和，初始为 0。
seen (哈希表): 这用于在 O(1) 的时间复杂度内判断一个元素是否已经存在于当前窗口中。

算法流程如下：

初始化 left = 0, max_score = 0, current_sum = 0, seen = {} (一个空的哈希集合)。
让 right 指针从 0 开始遍历整个数组，直到数组末尾。在每一步中，我们处理 nums[right] 这个元素。如果重复了就缩进左边直到去除重复元素。然后每一步将 right 右移，途中注意加和和哈希表的处理。
当 right 指针遍历完整个数组后，max_score 中存储的就是最终的结果。

代码实现

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int left = 0; //左指针
        int right = 0; //右指针
        unordered_set<int> aggregation; // 检查是否存在的无序集合
        int result = 0; // 计算结果
        int max = 0; // 储存最大值 
        for(right; right < nums.size(); right++) //右指针遍历
        {
            if(aggregation.count(nums[right])) 
            // 如果元素已经存在（扫描到重复元素）
            {
                while(nums[left] != nums[right])
                // 直到左缩进到重复元素
                {
                    result = result - nums[left];
                    aggregation.erase(nums[left]);
                    left++;
                }
                // 这时左指针在重复元素处，需要再缩进一步
                result = result - nums[left];
                left++;
            }
            //正常情况，把右指针加入即可
            result = result + nums[right];
            if(result > max)
                max = result;
            aggregation.insert(nums[right]);
        }
        return max;
    }
};

进一步优化思路

哈希表虽然好用，但它有固有的开销。对于这道题，因为给出的数据结构本就很简单，为 int，那么我们可以利用题目给出的一个隐藏条件：nums 中元素的取值范围是有限的（ 1 <= nums[i] <= 10000）。当元素的范围可控时，我们可以用一个数组来模拟哈希集合的功能，这会快得多，直接避免了哈希计算的过程。

优化代码

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(NULL);

        int left = 0; //左指针
        int right = 0; //右指针
        bool aggregation[10001] = {false}; // 检查是否存在的无序集合
        int result = 0; // 计算结果
        int max = 0; // 储存最大值 

        for(right; right < nums.size(); right++) //右指针遍历
        {
            if(aggregation[nums[right]]) 
            // 如果元素已经存在（扫描到重复元素）
            {
                while(aggregation[nums[right]])
                // 直到左缩进到重复元素
                {
                    result = result - nums[left];
                    aggregation[nums[left]] = 0;
                    left++;
                }
            }
            //正常情况，把右指针加入即可
            result = result + nums[right];
            if(result > max)
                max = result;
            aggregation[nums[right]] = 1;
        }
        return max;
    }
};

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

beautifulremi

题目

思路

代码实现

进一步优化思路

优化代码