एक सरणी गिरफ्तारी [] जिसमें सकारात्मक पूर्णांक दिए गए हैं। लक्ष्य कम से कम 1 लंबाई के उप-सरणियों की संख्या ज्ञात करना है जो गैर-बढ़ती हैं। अगर arr[]={1,3,2}, तो उप-सरणी {1}, {2}, {3}, {3,2} होंगी। गिनती 4 है।
उदाहरण के लिए
इनपुट
arr[] = {5,4,5}
आउटपुट
Count of number of non-increasing subarrays are: 7
स्पष्टीकरण
The subarrays will be − {5}, {4}, {5}, {5,4}
इनपुट
arr[] = {10,9,8,7}
आउटपुट
Count of number of non−increasing subarrays are − 10
स्पष्टीकरण
The subarrays will be − {10}, {9}, {8}, {7}, {10,9}, {9,8}, {8,7}, {10,9,8}, {9,8,7}, {10,9,8,7}
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में, हम इस तथ्य का उपयोग करेंगे कि यदि arr[] में अनुक्रमणिका i और j के बीच के तत्व गैर-बढ़ते नहीं हैं तो अनुक्रमणिका i से j+1, i से j+2….i से j+n−1 के बीच के तत्व कभी भी गैर-बढ़ती नहीं हो सकती है इसलिए इस सबरे की लंबाई को तब तक बढ़ाते रहें जब तक कि तत्व न बढ़ रहे हों। यदि कोई कम तत्व पाया जाता है arr[j]
-
एक पूर्णांक सरणी arr[] लें।
-
फ़ंक्शन सबएरे (int arr [], int size) सरणी और उसके आकार को लेता है और गैर-बढ़ती उपसरणियों की संख्या की गिनती देता है।
-
प्रारंभिक गणना को 0 के रूप में और सबसे छोटी उपसरणी की लंबाई को अस्थायी =1 के रूप में लें।
-
ट्रैवर्स एआर [] लूप के लिए उपयोग कर रहा है, अगर एआर [i + 1] <=एआर [i] तो सबरे के रूप में वृद्धि अस्थायी रूप से बढ़ रही है।
-
अन्यथा (अस्थायी + 1) * अस्थायी) / 2 जोड़ें ताकि लंबाई अस्थायी के सबरे की संख्या की गणना की जा सके जो गैर-बढ़ती है।
-
नए उप-सरणी के लिए अस्थायी =1 सेट करें।
-
सभी लूपों के अंत में, यदि लंबाई अस्थायी>1 फिर से जोड़ें (अस्थायी + 1) * अस्थायी) / 2 अंतिम सबरे के लिए गिनने के लिए।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
#include <bits/stdc++.h> using namespace std; int subarrays(int arr[], int size){ int count = 0; int temp = 1; for(int i = 0; i < size − 1; ++i){ if (arr[i + 1] <= arr[i]){ temp++; } else { count += (((temp + 1) * temp) / 2); temp = 1; } } if(temp > 1){ count += (((temp + 1) * temp) / 2); } return count; } int main(){ int arr[] = {2, 6, 1, 8, 3}; int size = sizeof(arr) / sizeof(arr[0]); cout<<"Count of number of non−increasing subarrays are: "<<subarrays(arr, size); return 0; }
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count the number of non-increasing subarrays are: 7