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

Chúng ta được cung cấp một mảng arr [] các số nguyên. Cũng là một số K. Mục đích là đếm tất cả các mảng con của arr [] sao cho tất cả các phần tử của mảng con lớn hơn K hoặc K nhỏ hơn tất cả các phần tử của mảng con. Nếu mảng là [1,2,3] và K là 1. Các mảng con sẽ là [2], [3], [2,3].

Hãy cho chúng tôi hiểu với các ví dụ.

Đầu vào - arr [] ={2, 2, 1, 1, 1, 5}; K =1

Đầu ra - Tổng số mảng con có tất cả các phần tử lớn hơn K là - 4

Giải thích - Các tham số con sẽ là:[2], [2], [5], [2,2]. Tất cả các phần tử trong mỗi mảng con đều lớn hơn 1.

Đầu vào - arr [] ={3,4,5,6}; K =2

Đầu ra - Tổng số mảng con có tất cả các phần tử lớn hơn K là - 10

Giải thích - Các tham số con sẽ là - [3], [4], [5], [6], [3,4], [4,5], [5,6], [3,4,5], [4, 5,6], [3,4,5,6]. Tổng số =10.

Cách tiếp cận được sử dụng trong chương trình dưới đây như sau

Chúng ta sẽ duyệt qua mảng bằng vòng lặp for. Nếu phần tử hiện tại lớn hơn K. Tăng đếm. Nếu không thì đặt count =0 và total =count * (count + 1) / 2. (dành cho mảng con). Nếu ở cuối số đếm là khác không. Thêm số lượng * (số lượng + 1) / 2 để biết số lượng các mảng con còn lại.

• Lấy một mảng [] số.

• Hàm sub_greater_k (int arr [], int size, int k) nhận mảng và trả về số lượng các mảng con có tất cả các phần tử lớn hơn k.

• Lấy số lượng ban đầu là 0.

• Chúng tôi sẽ duyệt qua mảng bằng cách sử dụng vòng lặp for từ i =0 đến i

• Nếu arr [i]> k thì số gia tăng.

• Các mảng con có số đếm (phần tử> k) sẽ được đếm * (số đếm + 1) / 2. Thêm điều này vào tổng số cho tất cả các mảng con như vậy.

• Khi kết thúc một lần nữa, hãy thêm số lượng * (số đếm + 1) / 2 vào tổng số nếu số lượng khác 0.

• Kết quả là trả về tổng số.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int sub_greater_k(int arr[], int size, int k){
   int count = 0;
   int 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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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