数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中非递增子数组的计数
给定一个包含正整数的数组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……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
更新于：2021年1月5日
286 次浏览
广告