C++で指定された条件を満たすインデックスペアをカウントします

最初のN個の自然数の順列の配列が与えられます。ここでの目標は、以下の条件を満たす要素のインデックスペアを見つけることです-

配列がArr[]の場合、i、jはインデックスであり、i <=x<=j。>

つまり、Arr[i]とA[j]の合計は、これら2つのセグメント間で発生する最大要素に等しくなります。

入力

Arr[]= { 2,4,1,3,6,5 }

出力

Count of index pairs which satisfy the given condition:1

説明 −ペアの合計が与えられます-

2 + 4 =6、6は最大ですが、2から4の間ではありません。

2 + 1 =3、3は2と1の間になく、それらの間の最大値は4です。

2 + 3 =5、5は2と3の間になく、それらの間の最大値は4です。

2 + 6 =8、8は2と6の間になく、それらの間の最大値は4です。

同様に

1 + 5 =6、6は1から5の間にあり、それらの間の最大値は6です。

すべてのうち、条件を満たすのは1つのペアだけです。

入力

Arr[]= { 1,2,5,4,3 }

出力

Count of index pairs which satisfy the given condition:2

説明 −ペアの合計が与えられます-

1 + 5 =6、6は最大ですが、1から5の間ではありません。

1 + 4 =5、5は1から4の間にあり、それらの間の最大値は5です。

2 + 3 =5、5は2と3の間にあり、それらの間の最大値は5です。

1 + 3 =4、4は1と3の間にありますが、それらの間の最大値は5です。

条件を満たす2つのペアすべてが存在します。

以下のプログラムで使用されているアプローチは次のとおりです

• 整数配列Arr[]は、数値とその長さのサイズを格納します。

• 関数countPairs（int A []、int n）は、配列とそのサイズnを入力として受け取り、上記の条件を満たすペアの数を返します。

• 変数カウントは、そのようなペアの初期値0を格納するために使用されます。

• max1をmaxindexの最初の要素とそのインデックスで0として初期化し、これまでに見つかった最大値の値とインデックスを格納します。

• forループを使用してアレイのトラバースを開始します。

• A [j]> =max1が指定されている場合、ネストされたforループ内で、max1とそのインデックスをjで更新します。

• A[i]とA[j]の各ペアについて、合計がmax1に等しく、インデックスmaxindexがiとjの間にある場合、条件が満たされたときにカウントをインクリメントします。

• 終了後、両方のループがカウントに存在する結果を返します。

例

// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the count of
// required index pairs
int countPairs(int A[], int n){
   // To store the required count
   int count = 0;
   int i,j,k;
   int max1=A[0];
   int maxindex=0;
   for ( i = 0; i<n-1; i++){
      for(j=i+1;j<n;j++){
         if(A[j]>=max1){
             max1=A[j];
            maxindex=j;
      }
      if(A[i]+A[j]==max1 && maxindex>=i && maxindex<=j)
         count++;
      }
   }
   // Return count of subsegments
   return count;
}
int main(){
   int Arr[] = {3, 4, 6, 1, 5, 2};
   int size =6;
   cout <<endl<<"Count of index pairs which satisfy the given condition:"
   <<countPairs(Arr,size);
   return 0;
}

出力

Count of index pairs which satisfy the given condition:1