C++에서 엄격하게 감소하는 하위 배열의 수 찾기

배열 A가 있다고 가정합니다. 길이가> 1인 엄격하게 감소하는 하위 배열의 총 수를 찾아야 합니다. 따라서 A =[100, 3, 1, 15]인 경우. 따라서 감소 시퀀스는 [100, 3], [100, 3, 1], [15]이므로 출력은 3이 됩니다. 3개의 하위 배열이 발견되면

아이디어는 len l의 하위 배열을 찾고 결과에 l(l – 1)/2를 추가하는 것입니다.

예

#include<iostream>
using namespace std;
int countSubarrays(int array[], int n) {
   int count = 0;
   int l = 1;
   for (int i = 0; i < n - 1; ++i) {
      if (array[i + 1] < array[i])
         l++;
      else {
         count += (((l - 1) * l) / 2);
         l = 1;
      }
   }
   if (l > 1)
   count += (((l - 1) * l) / 2);
   return count;
}
int main() {
   int A[] = { 100, 3, 1, 13, 8};
   int n = sizeof(A) / sizeof(A[0]);
   cout << "Number of decreasing subarrys: " << countSubarrays(A, n);
}

출력

Number of decreasing subarrys: 4