查找C ++中严格减少的子数组的数量

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个数组A。而且我们必须找到长度> 1的严格递减子数组的总数。因此，如果A = [100，3，1，15]。因此，递减的顺序为[100，3]，[100，3，1]，[15]。由于找到了三个子数组，因此输出为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

以上是 查找C ++中严格减少的子数组的数量 的全部内容， 来源链接： utcz.com/z/340874.html