C++での最大消去値

正の整数の配列が与えられた場合、タスクはすべての一意の要素を含むサブ配列を消去することです。サブアレイを消去することで得られるものは、その要素の合計に等しくなります。

現在のサブアレイの前後の項を消去して最大合計を返します。1つのサブアレイを正確に消去することで最大合計を取得できます。

配列arr aのサブ配列と呼ばれます aの連続したサブシーケンスを形成する場合 つまり、一部の（l、r）のa [l]、a [l + 1]、...、a[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}です。

この問題を解決するためのアプローチ

この問題を解決するために、スライディングウィンドウの概念を使用します。この手法は、ネストされたループを単一のループに変換して、時間の複雑さを軽減する方法を示しています。

この手法では、最初に（左と右）の2つのポインタと、ウィンドウのサイズを「win」として初期化します。配列を反復処理しながら、特定の勝利のサイズが最大かどうかを確認します。最大値が見つかった場合は、出力として返します。

この問題を解決するためのアプローチ

• 正の整数の配列を入力してください。

• 整数関数maximumUniqueSubarray（vector＆arr）は、配列を入力として受け取ります。

• 3つのポインター「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