C++で増加しないサブ配列の数を数えます

正の整数を含む配列arr[]が与えられます。目標は、増加しない長さのサブアレイの数を少なくとも1つ見つけることです。 arr [] ={1,3,2}の場合、サブ配列は{1}、{2}、{3}、{3,2}になります。カウントは4です。

例

入力

arr[] = {5,4,5}

出力

Count of number of non-increasing subarrays are: 7

説明

The subarrays will be −
{5}, {4}, {5}, {5,4}

入力

arr[] = {10,9,8,7}

出力

Count of number of non−increasing subarrays are − 10

説明

The subarrays will be −
{10}, {9}, {8}, {7}, {10,9}, {9,8}, {8,7}, {10,9,8}, {9,8,7}, {10,9,8,7}

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

このアプローチでは、arr []のインデックスiとjの間の要素が増加しない場合、インデックスiからj + 1、iからj+2….iからj+n-1の間の要素を使用します。増加しないことは決してないので、要素が増加しなくなるまで、このサブ配列の長さを増やし続けます。より小さな要素が見つかった場合は、arr [j]

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

• 関数subarrays（int arr []、int size）は、配列とそのサイズを取得し、増加しないサブ配列の数のカウントを返します。

• 初期カウントを0とし、最小サブアレイの長さをtemp=1とします。

• forループを使用してarr[]をトラバースし、arr [i + 1] <=arr [i]の場合、サブ配列が増加しないため、温度を増加させます。

• それ以外の場合は、（temp + 1）* temp）/ 2を追加して、増加しない長さtempのサブアレイのサブレイの数をカウントします。

• 新しいサブアレイにはtemp=1を設定します。

• すべてのループの最後で、長さtemp> 1の場合、最後のサブアレイをカウントするために（temp + 1）* temp）/2を再度追加します。

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

例

#include <bits/stdc++.h>
using namespace std;
int subarrays(int arr[], int size){
   int count = 0;
   int temp = 1;
   for(int i = 0; i < size − 1; ++i){
      if (arr[i + 1] <= arr[i]){
         temp++;
      } else {
         count += (((temp + 1) * temp) / 2);
         temp = 1;
      }
   }
   if(temp > 1){
      count += (((temp + 1) * temp) / 2);
   }
   return count;
}
int main(){
   int arr[] = {2, 6, 1, 8, 3};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of number of non−increasing subarrays are: "<<subarrays(arr, size);
   return 0;
}

出力

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

Count the number of non-increasing subarrays are: 7