정수 요소와 변수 k를 포함하는 배열 arr[]이 제공됩니다. 목표는 k보다 더 큰/최대 요소를 갖는 arr[]의 하위 배열의 수를 찾는 것입니다. 배열이 [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라는 것을 알고 있습니다.
이제 요소가
-
정수 배열 arr[] 및 변수 k를 입력으로 사용합니다.
-
함수 maximum_k(int arr[], int size, int k)는 배열, k 및 배열의 길이를 가져와서 최대 요소가 k보다 큰 하위 배열의 개수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
while 루프를 사용하여 인덱스 i=0에서 i
-
각 요소에 대해 arr[i]>k이면 계속 문을 사용하여 건너뜁니다.
-
그렇지 않으면 내부 while 루프를 사용하여 하위 배열의 길이 계산을 시작합니다.
-
arr[i]
-
내부의 끝에서 현재 하위 배열의 길이를 temp로 사용합니다.
temp*(temp+1)/2를 계산하고 카운트에 추가합니다.
-
이러한 모든 하위 배열에 대해 이 작업을 수행합니다.
-
외부 while의 끝에서. 요소가
-
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