Đếm số subarray có phần tử lớn nhất lớn hơn k trong C++

Cho mảng arr[] và số k. Đếm subarray có phần tử lớn nhất > k. Ví dụ: [1,2,3], k=1 → subarray: [1],[2],[3],[1,2],[2,3],[1,2,3]. Các subarray max > 1: [2],[3],[1,2],[2,3],[1,2,3] → 5.

Ví dụ

Đầu vào − arr[] = {1,2,5,3}, k=3

Đầu ra − 6

Giải thích − Subarray chứa 5: [5], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3].

Đầu vào − arr[] = {1,2,3,4,5}, k=4

Đầu ra − 5

Giải thích − Chỉ có 5 > 4. Subarray chứa 5: [5], [4,5], [3,4,5], [2,3,4,5], [1,2,3,4,5].

Phương pháp giải

Tổng subarray = n*(n+1)/2. Đếm subarray toàn bộ phần tử ≤ k (bỏ qua phần tử > k). Với mỗi đoạn liên tiếp độ dài l toàn ≤ k, số subarray = l*(l+1)/2. Trừ khỏi tổng.

• Hàm maximum_k(int arr[], int size, int k).
• count = 0.
• Duyệt i = 0..size-1:
  • Nếu arr[i] > k: i++, continue.
  • Đếm temp = độ dài đoạn liên tiếp ≤ k.
  • count += temp*(temp+1)/2.
• count = size*(size+1)/2 - count.
• Trả về count.

Ví dụ code

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

int maximum_k(int arr[], int size, int k) {
    int count = 0;
    int i = 0;
    while (i < size) {
        if (arr[i] > k) { i++; continue; }
        int temp = 0;
        while (i < size && arr[i] <= k) { i++; temp++; }
        count += temp * (temp + 1) / 2;
    }
    count = size * (size + 1) / 2 - count;
    return count;
}

int main() {
    int arr[] = {4, 1, 2, 7, 8, 3};
    int k = 5;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of subarrays whose maximum element is greater than k are: " << maximum_k(arr, size, k);
    return 0;
}

Đầu ra

Count of subarrays whose maximum element is greater than k are: 14