在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

说明-Subaarays将是-[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 <size的for循环遍历数组。

• 如果arr [i]> k，则增加计数。

• 具有count（元素> k）的子数组将为count *（count + 1）/ 2。将其添加到所有此类子数组的总数中。

• 如果计数不为零，则再次在总数末添加count *（count + 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