数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律C++ 中求最大元素大于 k 的子数组个数
给定一个包含整数元素的数组 arr[] 和一个变量 k。目标是找到 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 的子数组的长度）。
在内部 while 循环结束时，我们将 temp 作为当前子数组的长度。
计算 temp*(temp+1)/2 并添加到计数中。
对所有此类子数组执行此操作。
在外部 while 循环结束时。我们有变量 count 作为所有元素都小于 k 的子数组的个数。
通过从 arr[] 的所有可能的子数组个数（即 size*(size-1)/2）中减去此计数来更新计数。
返回 count 作为结果。
示例
#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
273 次浏览
