C++で最大要素がkより大きいサブ配列の数

整数要素と変数kを含む配列arr[]が与えられます。目標は、kを超える最大/最大要素を持つarr[]のサブ配列の数を見つけることです。配列が[1,2,3]で、kが1の場合、可能なサブ配列は[1]、[2]、[3]、[1,2]、[2,3]、[1,2,3]です。 ]。最大要素が1より大きいサブ配列は、[2]、[3]、[1,2]、[2,3]、[1,2,3]です。したがって、カウントは5です。

例を挙げて理解しましょう

入力 − arr [] ={1,2,5,3} k =3

出力 −最大要素がkより大きいサブアレイの数は− 6

説明 −可能なすべてのサブ配列は、[1]、[2]、[5]、[3]、[1,2]、[2,5]、[5,3]、[1,2,5]、[2、 5,3]、[1,2,5,3]。最大要素が3より大きいこれらの配列のうち、5が含まれている配列があります。それらは-

[5]、[2,5]、[5,3]、[1,2,5]、[2,5,3]、[1,2,5,3]。

合計6つのサブアレイ。

入力 − arr [] ={1,2,3,4,5} k =4

出力 −最大要素がkより大きいサブアレイの数は− 5

説明 −4より大きい要素のみが5です。5を含むサブ配列は-

[5]、[4,5]、[3,4,5]、[2,3,4,5]、[1,2,3,4,5]。

合計5つのサブアレイ。

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

このアプローチでは、n個の要素を持つ配列のサブ配列の総数はn *（n + 1）/2であることがわかります。

ここで、要素がk未満のサブ配列を探します。このために、要素> kをスキップし、すべての要素がk未満のサブ配列の長さをカウントします。長さlごとに、各サブアレイはl *（l + 1）/2サブアレイを作成できます。このようなサブアレイごとにこの値を加算してXとします。最後に、この値Xをn *（n + 1）/ 2から減算して、目的の結果を取得します。

• 整数配列arr[]と変数kを入力として受け取ります。

• 関数maximum_k（int arr []、int size、int k）は、配列、k、および配列の長さを取り、最大要素がkより大きいサブ配列の数を返します

• 初期カウントを0とします。

• whileループを使用して、配列をインデックスi=0からiまでトラバースします。

• 各要素について、arr [i]> kの場合は、continueステートメントを使用してスキップします。

• それ以外の場合は、内側のwhileループを使用してサブアレイの長さのカウントを開始します。

• arr[i]

• 現在のサブアレイの長さをtempとして保持している間、内部の終わりに。

  temp *（temp + 1）/ 2を計算し、カウントに追加します。

• そのようなすべてのサブアレイに対してこれを行います。

• アウターの終わりに。要素がのすべてのサブ配列の数として変数countがあります。

• arr []のすべての可能なサブ配列の数、つまりsize *（size-1）/ 2からこの数を引くことにより、数を更新します。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int maximum_k(int arr[], int size, int k){
   int count = 0;
   int i = 0;
   while (i < size){
      if (arr[i] > k){
         i++;
         continue;
      }
      int temp = 0;
      while (i < size && arr[i] <= k){
         i++;
         temp++;
      }
      int temp_2 = temp * (temp + 1);
      count = count + temp_2 / 2;
   }
   count = (size * (size + 1) / 2 - count);
   return count;
}
int main(){
   int arr[] = { 4, 1, 2, 7, 8, 3 };
   int k = 5;
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subarrays whose maximum element is greater than k are: "<<maximum_k(arr, size, k);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of subarrays whose maximum element is greater than k are: 14