C++ 中的最大擦除值

给定一个正整数数组，任务是擦除包含所有唯一元素的子数组。擦除子数组后得到的值等于其元素之和。

通过擦除其之前或之后的项来返回当前子数组的最大和，我们可以通过精确擦除一个子数组来获得最大和。

如果数组**arr**构成**a**的连续子序列，则称其为**a**的子数组，即如果它等于a[l]，a[l+1]，…，a[r]对于某些(l,r)。例如，

**输入-1** −

arr[ ] = { 1,2,4,5,6 }

**输出** −

17

**说明** − 最优子数组是 {2,4,5,6}。

**输入-2** −

arr[ ]= {5,3,1,3,5,3,1,3,5}

**输出** −

9

**说明** − 最优子数组是 {5,3,1} 或 {1,3,5}。

解决此问题的方法

为了解决这个问题，我们将使用滑动窗口的概念。此技术展示了如何将嵌套循环转换为单个循环以减少时间复杂度。

在此技术中，我们将首先初始化两个指针（左和右）以及窗口大小为“win”。在遍历数组时，我们将检查特定 win 的大小是否最大。如果我们发现它最大，我们将将其作为输出返回。

解决此问题的方法：

• 输入一个正整数数组。

• 整数函数 maximumUniqueSubarray(vector&arr) 以数组作为输入。

• 取三个指针“I”、“j”和窗口大小“win”，遍历数组并查找当前窗口中是否存在元素在 HashSet 中，然后移动窗口并再次检查另一个元素。如果不存在，则将其插入到 HashSet 中并递减窗口大小，从而删除之前的元素。

• 找到结果和窗口值中的最大值。

• 返回结果。

示例

#include<bits/stdc++.h>
using namespace std;
int maximumUniqueSubarray(vector<int>& arr) {
   int result = 0;
   unordered_set<int> hashset;
   for (int i = 0, j = 0, win = 0; j < arr.size(); j++) {
      while (hashset.find(arr[j]) != hashset.end()) {
         hashset.erase(arr[i]);
         win -= arr[i];
         i++;
      }
      hashset.insert(arr[j]);
      win += arr[j];
      result = max(result, win);
   }
   return result;
}
int main(){
   vector<int>nums;
   nums<<5,3,1,3,5,3,1,3,5;
   cout<<maximumUniqueSubarray(nums)<<endl;
   return 0;
}

输出

运行上述代码将生成以下输出：

9

Kiran P

更新于：2021年2月4日

浏览量：180

开始您的职业生涯

完成课程获得认证

开始