정수 배열 arr[]이 제공됩니다. 또한 숫자 K입니다. 목표는 하위 배열의 모든 요소가 K보다 크거나 K가 하위 배열의 모든 요소보다 작도록 ar[]의 모든 하위 배열을 계산하는 것입니다. 배열이 [1,2,3]이고 K가 1인 경우 하위 배열은 [2], [3], [2,3]입니다.
예를 들어 이해합시다.
입력 - arr[] ={ 2, 2, 1, 1, 1, 5 }; K=1
출력 − K보다 큰 모든 요소가 있는 하위 배열의 개수는 − 4
입니다.설명 - 하위 배열은 [2], [2], [5], [2,2]입니다. 각 하위 배열의 모든 요소는 1보다 큽니다.
입력 - arr[] ={ 3,4,5,6 }; K=2
출력 − K보다 큰 모든 요소가 있는 하위 배열의 개수는 − 10입니다.
설명 - 하위 배열은 - [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로 설정합니다. (하위 배열의 경우). 종료 시 개수가 0이 아닌 경우. 남아 있는 하위 배열의 수에 대해 count*(count+1)/2를 추가합니다.
-
숫자의 배열 arr[]를 가져옵니다.
-
함수 sub_greater_k(int arr[], int size, int k)는 배열을 취하여 k보다 큰 모든 요소를 포함하는 하위 배열의 개수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
for 루프를 사용하여 i=0에서 i
-
arr[i]>k이면 카운트를 증가시킵니다.
-
개수가 있는 하위 배열(요소> k)은 개수*(count+1)/2가 됩니다. 이러한 모든 하위 배열의 합계에 이것을 추가합니다.
-
카운트가 0이 아닌 경우 다시 끝에 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