양의 정수를 포함하는 배열 arr[]이 제공됩니다. 목표는 증가하지 않는 길이가 1 이상인 부분배열의 수를 찾는 것입니다. arr[]={1,3,2}인 경우 하위 배열은 {1}, {2}, {3}, {3,2}가 됩니다. 개수는 4입니다.
예를 들어
입력
arr[] = {5,4,5} 출력
Count of number of non-increasing subarrays are: 7
설명
The subarrays will be −
{5}, {4}, {5}, {5,4}입니다. 입력
arr[] = {10,9,8,7} 출력
Count of number of non−increasing subarrays are − 10
설명
The subarrays will be −
{10}, {9}, {8}, {7}, {10,9}, {9,8}, {8,7}, {10,9,8}, {9,8,7}, {10,9,8,7} 아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
이 접근 방식에서 우리는 arr[]의 인덱스 i와 j 사이의 요소가 비증가하지 않는 경우 인덱스 i에서 j+1, i에서 j+2… 증가하지 않을 수 있으므로 요소가 증가하지 않을 때까지 이 하위 배열의 길이를 계속 증가시키십시오. 더 작은 요소가 발견되면 arr[j]
정수 배열 arr[]를 가져옵니다.
함수 subarrays(int arr[], int size)는 배열과 그 크기를 취하고 증가하지 않는 하위 배열의 수를 반환합니다.
초기 개수를 0으로, 가장 작은 하위 배열의 길이를 temp=1로 취합니다.
for 루프를 사용하여 arr[] 탐색, arr[i + 1] <=arr[i]이면 하위 배열이 증가하지 않으므로 temp를 증가시킵니다.
그렇지 않으면 (temp + 1) * temp) / 2를 추가하여 증가하지 않는 temp 길이의 하위 배열 수를 계산합니다.
새 하위 배열에 대해 temp=1을 설정합니다.
모든 루프의 끝에서 길이 temp>
1인 경우 다시 (temp + 1) * temp) / 2를 추가하여 마지막 하위 배열을 계산합니다.
결과로 카운트를 반환합니다.
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
예시
#include <bits/stdc++.h>
using namespace std;
int subarrays(int arr[], int size){
int count = 0;
int temp = 1;
for(int i = 0; i < size − 1; ++i){
if (arr[i + 1] <= arr[i]){
temp++;
} else {
count += (((temp + 1) * temp) / 2);
temp = 1;
}
}
if(temp > 1){
count += (((temp + 1) * temp) / 2);
}
return count;
}
int main(){
int arr[] = {2, 6, 1, 8, 3};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of number of non−increasing subarrays are: "<<subarrays(arr, size);
return 0;
} 출력
Count the number of non-increasing subarrays are: 7