C++でKより大きいすべての要素を持つサブ配列をカウントします

整数の配列arr[]が与えられます。また、数値Kです。目標は、arr []のすべてのサブ配列をカウントして、サブ配列のすべての要素がKより大きいか、Kがサブ配列のすべての要素よりも小さいようにすることです。配列が[1,2,3]で、Kが1の場合、サブ配列は[2]、[3]、[2,3]になります。

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

入力 − arr [] ={2、2、1、1、1、5}; K =1

出力 −すべての要素がKより大きいサブアレイの数は− 4

説明 − Subaaraysは、[2]、[2]、[5]、[2,2]になります。各サブアレイのすべての要素が1より大きい。

入力 − arr [] ={3,4,5,6}; K =2

出力 −すべての要素がKより大きいサブアレイの数は− 10

説明 −サブアレイは− [3]、[4]、[5]、[6]、[3,4]、[4,5]、[5,6]、[3,4,5]、[4、 5,6]、[3,4,5,6]。総数=10。

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

forループを使用して配列をトラバースします。現在の要素がKより大きい場合。インクリメントカウント。それ以外の場合は、count=0およびtotal=count *（count + 1）/2に設定します。 （サブアレイの場合）。最後にカウントがゼロ以外の場合。残りのサブアレイのカウントにcount*（count + 1）/2を追加します。

• 数字の配列arr[]を取ります。

• 関数sub_greater_k（int arr []、int size、int k）は配列を受け取り、すべての要素がkより大きいサブ配列の数を返します。

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

• i=0からi

• arr [i]> kの場合、カウントをインクリメントします。

• count（要素> k）のサブ配列はcount *（count + 1）/2になります。これをそのようなすべてのサブアレイの合計に追加します。

• カウントがゼロ以外の場合は、最後にカウント*（カウント+ 1）/2を合計に追加します。

• 結果として合計を返します。

例

#include <bits/stdc++.h>
using namespace std;
int sub_greater_k(int arr[], int size, int k){
   int count = 0;
   int total = 0;
   for (int i = 0; i < size; i++){
      if (arr[i] > k){
         count++;
      }
      else{
         total += (count) * (count + 1) / 2;
         count = 0;
      }
   }
   if(count){
      total += (count) * (count + 1) / 2;
   }
   return total;
}
int main(){
   int arr[] = {2, 4, 6, 1, 3, 7, 9 };
   int size = sizeof(arr) / sizeof(arr[0]);
   int k = 7;
   cout<<"Count of subarrays with all elements greater than K are: "<<sub_greater_k(arr, size, k);
   return 0;
}

出力

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

Count of subarrays with all elements greater than K are: 1