サブ配列を否定した後に取得できる個別の値の数を見つけるためのC++プログラム

n個の要素を持つ配列Aがあるとします。与えられた数のサブセットを選択し、これらの数を否定します。取得できる配列内のさまざまな値の最大数を見つける必要があります。

したがって、入力がA =[1、1、2、2]の場合、出力は4になります。これは、最初と最後の数値を否定して、配列[-1、1、2、-2]を作成できるためです。 4つの異なる値。

ステップ

これを解決するには、次の手順に従います-

Define one set se
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   x := A[i]
   if x is present in se, then:
      insert -x into se
   Otherwise
      insert x into se
return size of se

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
   set<int> se;
   int n = A.size();
   for (int i = 0; i < n; i++) {
      int x = A[i];
      if (se.count(x))
         se.insert(-x);
      else
         se.insert(x);
   }
   return se.size();
}
int main() {
   vector<int> A = { 1, 1, 2, 2 };
   cout << solve(A) << endl;
}

入力

{ 1, 1, 2, 2 }

出力

4