Đếm số mảng con giảm chặt trong C++

Giả sử có mảng A. Tìm tổng số mảng con giảm chặt độ dài > 1. Nếu A = [100, 3, 1, 15]. Các dãy giảm: [100, 3], [100, 3, 1], [15] Kết quả 3 vì tìm thấy 3 mảng con.

Ý tưởng là tìm mảng con độ dài l và cộng l(l-1)/2 vào kết quả.

Ví dụ mã nguồn

#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); }

Kết quả

Number of decreasing subarrys: 4