Tìm số đoạn (segments) mà tất cả phần tử lớn hơn X bằng C++

Cho mảng arr[] và số X, đếm số đoạn con liên tiếp (subarray/segment) mà mọi phần tử trong đoạn đều > X. Các đoạn chồng lặp chỉ đếm một lần, đoạn liên tiếp không tách riêng.

Ví dụ

Input: arr[] = {9, 6, 7, 11, 5, 7, 8, 10, 3}, X = 7 Output: 3
Các đoạn: {9}, {11}, {8, 10}

Input: arr[] = {9, 6, 12, 2, 11, 14, 8, 14}, X = 8 Output: 4
Các đoạn: {9}, {12}, {11, 14}, {14}

Phương pháp

Dùng biến state như công tắc: state = 1 khi đang trong đoạn > X, state = 0 khi gặp phần tử ≤ X. Mỗi khi state chuyển từ 1 → 0, tăng đếm. Cuối mảng nếu state = 1 cũng tăng đếm.

Mã nguồn C++

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

int main() {
    int a[] = {9, 6, 12, 2, 11, 14, 8, 14};
    int n = sizeof(a) / sizeof(a[0]);
    int X = 8;
    int state = 0;
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (a[i] > X) {
            state = 1;
        } else {
            if (state)
                count += 1;
            state = 0;
        }
    }
    if (state)
        count += 1;

    cout << "Số đoạn tất cả phần tử > X: " << count;
    return 0;
}

Kết quả

Số đoạn tất cả phần tử > X: 4

Giải thích

Biến state đóng vai trò công tắc. Gặp phần tử > X → bật (1). Gặp phần tử ≤ X → nếu đang bật thì tăng đếm và tắt (0). Cuối mảng kiểm tra lại nếu vẫn đang bật. Độ phức tạp O(N), không gian O(1).

Kết luận

Bài viết giải quyết bài toán đếm đoạn con toàn bộ phần tử > X bằng kỹ thuật state machine đơn giản. Mã nguồn C++ ngắn gọn, hiệu quả. Có thể viết bằng C, Java, Python.