在C ++中最大元素大于k的子数组的数量
给我们一个包含整数元素和变量k的数组arr []。目的是找到arr []的最大/最大元素多于k的子数组的数量。如果数组是[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。现在，我们最后从n *（n + 1）/ 2中减去此值X，以获得所需的结果。
以整数数组arr []和变量k作为输入。
函数maximum_k（int arr []，int size，int k）接受数组，k和数组的长度，并返回最大元素大于k的子数组的计数
将初始计数设为0。
使用while循环，遍历数组从索引i = 0到i <size。
对于arr [i]> k的每个元素，请使用continue语句将其跳过。
否则，开始使用内部while循环计算子数组的长度。
如果arr [i] <k并且i <size。递增i和temp（所有元素<k的子数组的长度）。
在内部的结尾，我们将当前子数组的长度设为temp。
计算temp *（temp + 1）/ 2并相加。
对所有此类子数组执行此操作。
在外一会结束时。我们具有变量count作为元素<k的所有子数组的数量。
通过从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
以上是 在C ++中最大元素大于k的子数组的数量 的全部内容， 来源链接： utcz.com/z/347116.html
