Chúng ta được cho một mảng arr [] chứa các phần tử nguyên và một biến k. Mục đích là tìm số lượng các mảng con của arr [] có phần tử lớn nhất / lớn nhất nhiều hơn k. Nếu mảng là [1,2,3] và k là 1. Thì các mảng con khả dĩ là [1], [2], [3], [1,2], [2,3], [1,2,3 ]. Các mảng con có phần tử lớn nhất> 1 là [2], [3], [1,2], [2,3], [1,2,3]. Vì vậy, số đếm là 5.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - arr [] ={1,2,5,3} k =3
Đầu ra - Số lượng các mảng con có phần tử lớn nhất lớn hơn k là - 6
Giải thích - Tất cả các mảng con có thể có là [1], [2], [5], [3], [1,2], [2,5], [5,3], [1,2,5], [2, 5,3], [1,2,5,3]. Trong số các mảng này có phần tử tối đa lớn hơn 3 là mảng có 5 phần tử trong đó. Đó là -
[5], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3].
Tổng số 6 mảng con.
Đầu vào - arr [] ={1,2,3,4,5} k =4
Đầu ra - Tổng số mảng con có phần tử lớn nhất lớn hơn k là - 5
Giải thích - Chỉ các phần tử lớn hơn 4 là 5. Các mảng con chứa 5 sẽ là -
[5], [4,5], [3,4,5], [2,3,4,5], [1,2,3,4,5].
Tổng số 5 mảng con.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Theo cách tiếp cận này, chúng ta biết rằng tổng số mảng con của mảng có n phần tử là n * (n + 1) / 2.
Bây giờ chúng ta sẽ tìm kiếm các mảng con có phần tử
-
Lấy mảng số nguyên arr [] và biến k làm đầu vào.
-
Hàm Maximum_k (int arr [], int size, int k) nhận mảng, k và độ dài của mảng và trả về số lượng các mảng con có phần tử tối đa lớn hơn k
-
Lấy số lượng ban đầu là 0.
-
Sử dụng vòng lặp while, duyệt mảng từ chỉ mục i =0 đến i
-
Đối với mỗi phần tử if arr [i]> k bỏ qua nó bằng cách sử dụng câu lệnh continue.
-
Nếu không, hãy bắt đầu đếm độ dài của mảng con bằng vòng lặp while bên trong.
-
Nếu arr [i]
-
Ở cuối bên trong trong khi chúng ta có độ dài của mảng con hiện tại là tạm thời.
Tính toán tạm thời * (temp + 1) / 2 và thêm vào số đếm.
-
Thực hiện việc này cho tất cả các mảng con như vậy.
-
Vào cuối bên ngoài while. Chúng tôi có số lượng biến là số lượng của tất cả các mảng con có phần tử
-
Cập nhật số lượng bằng cách trừ số lượng này cho tất cả các mảng con có thể có của arr [], đó là size * (size-1) / 2.
-
Kết quả là số lượt trả lại.
Ví dụ
#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++;
}
int temp_2 = temp * (temp + 1);
count = count + temp_2 / 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
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of subarrays whose maximum element is greater than k are: 14