Đếm mảng con có tất cả phần tử lớn hơn K trong C++

Cho mảng arr[] và số K. Đếm mảng con mà mọi phần tử đều > K. Ví dụ [1,2,3], K=1 → [2], [3], [2,3].

Ví dụ

Đầu vào: arr[] = {2, 2, 1, 1, 1, 5}, K = 1
Đầu ra: 4 ([2], [2], [5], [2,2]).

Đầu vào: arr[] = {3,4,5,6}, K = 2
Đầu ra: 10 (tất cả mảng con đều thỏa mãn).

Giải thuật

Duyệt mảng, đếm độ dài đoạn liên tiếp các phần tử > K. Với đoạn dài count, số mảng con là count * (count + 1) / 2. Cộng dồn.

Ví dụ triển khai

#include <bits/stdc++.h>
using namespace std;

int sub_greater_k(int arr[], int size, int k) {
    int count = 0, total = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] > k) count++;
        else {
            total += count * (count + 1) / 2;
            count = 0;
        }
    }
    if (count) total += count * (count + 1) / 2;
    return total;
}

int main() {
    int arr[] = {2, 4, 6, 1, 3, 7, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 7;
    cout << "Count of subarrays with all elements greater than K are: " << sub_greater_k(arr, size, k);
    return 0;
}

Kết quả

Count of subarrays with all elements greater than K are: 1