计算C ++中非递增子数组的数量

给定包含正整数的数组arr []。目标是找到长度不小于1的至少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….i与j + n-1之间的元素永远不能不增加，因此请保持增加此子数组的长度，直到元素不增加为止。如果找到任何较小的元素，则arr [j] <arr [j-1]然后加len *（len + 1）/ 2（当前非递增子数组中包含len个元素的子数组）来计数此类子数组并重置其长度子数组为1。

• 取一个整数数组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