हमें एक सरणी दी गई है arr[] जिसमें पूर्णांक तत्व और एक चर k है। लक्ष्य एआर के उप-सरणी की गिनती का पता लगाना है [] जिसमें सबसे बड़ा/अधिकतम तत्व अधिक है के। यदि सरणी [1,2,3] है और k 1 है। तब संभावित उप-सरणी हैं [1], [2], [3], [1,2], [2,3], [1,2,3 ]. अधिकतम तत्व> 1 के साथ उप-सरणी [2], [3], [1,2], [2,3], [1,2,3] हैं। तो गिनती 5 है।
आइए उदाहरणों के साथ समझते हैं
इनपुट - गिरफ्तारी [] ={1,2,5,3 } k=3
आउटपुट − उपसरणियों की संख्या जिनका अधिकतम तत्व k से बड़ा है − 6
स्पष्टीकरण -सभी संभावित उप-सरणी हैं [1], [2], [5], [3], [1,2], [2,5], [5,3], [1,2,5], [2, 5,3], [1,2,5,3]। इन सरणियों में से अधिकतम 3 से अधिक तत्वों वाले ऐसे सरणियाँ हैं जिनमें 5 हैं। वे हैं -
[5], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3]।
कुल 6 उप-सरणी।
इनपुट - गिरफ्तारी [] ={1,2,3,4,5 } k=4
आउटपुट − उपसरणियों की संख्या जिनका अधिकतम तत्व k से बड़ा है − 5
स्पष्टीकरण − केवल 4 से बड़े एलिमेंट 5 हैं। 5 वाले सबअरे होंगे -
[5], [4,5], [3,4,5], [2,3,4,5], [1,2,3,4,5]।
कुल 5 उप-सरणी।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम जानते हैं कि n तत्वों के साथ सरणी के उपसरणियों की कुल संख्या n*(n+1)/2 है।
अब हम ऐसे उप-सरणियों की तलाश करेंगे जिनमें तत्व
-
इनपुट के रूप में पूर्णांक सरणी arr[] और वेरिएबल k लें।
-
फ़ंक्शन max_k(int arr[], int size, int k) सरणी, k और सरणी की लंबाई लेता है और उन सबएरे की गिनती देता है जिसका अधिकतम तत्व k से बड़ा है
-
प्रारंभिक गणना 0 के रूप में लें।
-
लूप के दौरान, अनुक्रमणिका i=0 से i<आकार तक ट्रैवर्स सरणी का उपयोग करना।
-
प्रत्येक तत्व के लिए यदि arr[i]>k जारी रखें कथन का उपयोग करके इसे छोड़ दें।
-
अन्यथा एक आंतरिक जबकि लूप का उपयोग करके उपसरणी की लंबाई गिनना शुरू करें।
-
अगर गिरफ्तारी [i] <के और मैं <आकार। वृद्धि मैं और अस्थायी (सभी तत्वों के साथ उप-सरणी की लंबाई
-
आंतरिक के अंत में, जबकि हमारे पास वर्तमान उप-सरणी की लंबाई अस्थायी है।
temp*(temp+1)/2 की गणना करें और गिनती में जोड़ें।
-
ऐसा सभी उपसरणियों के लिए करें।
-
बाहरी समय के अंत में। हमारे पास तत्वों के साथ सभी उपसरणियों की संख्या के रूप में चर गणना है
-
एआर [], यानी आकार*(आकार-1)/2 की सभी संभावित उप-सरणी की संख्या से इस गिनती को घटाकर गिनती अपडेट करें।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
#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;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of subarrays whose maximum element is greater than k are: 14