資料結構
網路
關係型資料庫管理系統 (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
廣告