Số mảng con có giá trị lớn nhất trong khoảng [L,R] trong C++

Mô tả bài toán

Cho mảng A số dương và L, R. Đếm số mảng con liên tiếp mà phần tử lớn nhất nằm trong [L, R].

Ví dụ: A=[2,1,4,3], L=2, R=3 → kết quả 3 (mảng con: [2], [2,1], [3]).

Giải thuật O(n) một lần duyệt

Duy trì:

• dp = số mảng con kết thúc tại i thỏa mãn điều kiện.
• prev = chỉ số gần nhất có A[i] > R (ranh giới phải).

Khi duyệt i:

• Nếu A[i] < L: dp không đổi, cộng dp vào kết quả (mảng con kết thúc ở i vẫn hợp lệ nếu đã có max hợp lệ trước đó).
• Nếu A[i] > R: reset dp=0, cập nhật prev=i.
• Nếu L ≤ A[i] ≤ R: dp = i - prev, cộng dp vào kết quả.

Cài đặt C++

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

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        int res = 0, dp = 0, prev = -1;
        for (int i = 0; i < A.size(); i++) {
            if (A[i] < L && i > 0) res += dp;
            else if (A[i] > R) { prev = i; dp = 0; }
            else { dp = i - prev; res += dp; }
        }
        return res;
    }
};

int main() {
    vector<int> v = {2,1,4,3};
    Solution ob;
    cout << ob.numSubarrayBoundedMax(v, 2, 3); // 3
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(1).