本文共 1290 字，大约阅读时间需要 4 分钟。

1. 题目

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

来源：力扣（LeetCode）

链接：

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 先计算前缀和，方便后面快速获取
• 滑动窗口内的数字存入哈希set，如果当前数字在set中，则窗口左端点向右移动，直至左端点该数字出现

class Solution {
   public:    int maximumUniqueSubarray(vector
   
    & nums) {
           int ans = 0, i = 0, j = 0, n = nums.size();        vector
    
      presum(nums);        for(int i = 1; i < n; i++)             presum[i] += presum[i-1];//前缀和        unordered_set
     
       s;        while(j < n)        {
               if(s.find(nums[j]) == s.end())            {
                   s.insert(nums[j]);            }            else//存在nums[j]            {
                   while(nums[i] != nums[j])                {
                       s.erase(nums[i++]);                }                i++;//左端点和nums[j]一样的数跳过了            }            ans = max(ans, i>0 ? presum[j]-presum[i-1] : presum[j]);            j++;        }        return ans;    }};
     
    
   

720 ms 116.1 MB C++

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/111415907 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！