एक सरणी गिरफ्तारी [] जिसमें सकारात्मक पूर्णांक दिए गए हैं। लक्ष्य कम से कम 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