Đếm mảng con có tất cả phần tử nhỏ hơn hoặc bằng X trong C++

Cho mảng arr[] và số X. Đếm tất cả các mảng con của arr[] sao cho mọi phần tử trong mảng con đều ≤ X. Ví dụ mảng [1,2,3], X=2 → mảng con: [1], [2], [1,2].

Ví dụ

Đầu vào: arr[] = {4,3,2,1,6}, X = 3
Đầu ra: 6
Giải thích: [3], [2], [1], [3,2], [2,1], [3,2,1].

Đầu vào: arr[] = {3,6,2,7,1,8,5}, X = 5
Đầu ra: 4
Giải thích: [3], [2], [1], [5].

Giải thuật

Tạo mảng nhị phân temp_arr[] cùng kích thước: 1 nếu arr[i] <= X, ngược lại 0. Tìm các đoạn liên tiếp toàn 1. Với đoạn dài temp, số mảng con là temp * (temp + 1) / 2. Cộng dồn.

Ví dụ triển khai

#include <iostream>
using namespace std;

int sub_X(int arr[], int size, int x) {
    int count = 0, temp = 0;
    int temp_arr[size];
    for (int i = 0; i < size; i++) {
        temp_arr[i] = (arr[i] <= x) ? 1 : 0;
    }
    for (int i = 0; i < size; i++) {
        if (temp_arr[i] == 1) {
            int temp_2;
            for (temp_2 = i + 1; temp_2 < size; temp_2++) {
                if (temp_arr[temp_2] != 1) break;
            }
            temp = temp_2 - i;
            int temp_3 = temp * (temp + 1) / 2;
            count += temp_3;
            i = temp_2;
        }
    }
    return count;
}

int main() {
    int arr[] = {2, 6, 1, 10, 5, 3};
    int x = 4;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of sub-arrays which have elements less than or equal to X are: " << sub_X(arr, size, x);
    return 0;
}

Kết quả

Count of sub-arrays which have elements less than or equal to X are: 3