数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时装研究
法律研究查找 C++ 中严格递减子数组的计数
假设我们有一个数组 A。我们必须找出长度> 1 的所有严格递减子数组的总数。所以如果 A = [100, 3, 1, 15]。所以递减序列为 [100, 3]、[100, 3, 1]、[15]。所以输出为 3。因为找到了三个子数组。
这个想法是，找出长度为 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
更新于: 2019 年 12 月 19 日
206 次观看
广告