C ++中的最大擦除值

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

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

阵列ARR 被称为是一个子阵列一个如果它形成的连续子序列一个即如果它等于一个[1]，A [L + 1]，...，A [R]对于一些（升，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”。在遍历数组时，我们将检查特定胜利的大小是否最大。如果发现最大值，则将其作为输出返回。

解决这个问题的方法，

• 输入一个正整数数组。

• 整数函数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