数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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
更新于：2021年2月4日
浏览量：180
广告