धनात्मक पूर्णांकों वाली एक सरणी arr[] दी गई है। लक्ष्य कम से कम लंबाई 1 वाले उन सबएरे की संख्या ढूंढना है जो गैर-बढ़ते हैं। यदि arr[] = {1,3,2}, तो सबएरे होंगे {1}, {2}, {3}, {3,2}। गिनती 4 है।
उदाहरण के लिए
इनपुट
arr[] = {5,4,5} आउटपुट
Count of number of non-increasing subarrays are: 7
व्याख्या
सबएरे होंगे - {5}, {4}, {5}, {5,4} इनपुट
arr[] = {10,9,8,7} आउटपुट
Count of number of non-increasing subarrays are - 10
व्याख्या
सबएरे होंगे - {10}, {9}, {8}, {7}, {10,9}, {9,8}, {8,7}, {10,9,8}, {9,8,7}, {10,9,8,7} नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:
इस दृष्टिकोण में, हम इस तथ्य का उपयोग करेंगे कि यदि इंडेक्स i और j के बीच arr[] में एलिमेंट्स गैर-बढ़ते नहीं हैं तो इंडेक्स i से j+1, i से j+2... i से j+n-1 के बीच एलिमेंट्स कभी भी गैर-बढ़ते नहीं हो सकते इसलिए इस सबएरे की लंबाई को तब तक बढ़ाते रहें जब तक एलिमेंट्स गैर-बढ़ते हैं। यदि कोई छोटा एलिमेंट मिलता है arr[j] < arr[j-1] तो len*(len+1)/2 (वर्तमान गैर-बढ़ते सबएरे के सबएरे जिनमें len एलिमेंट्स हैं) को ऐसी सबएरे की गिनती में जोड़ें और सबएरे की लंबाई को 1 पर रीसेट करें।
एक पूर्णांक सरणी arr[] लें।
फ़ंक्शन subarrays(int arr[], int size) सरणी और उसका आकार लेता है और गैर-बढ़ते सबएरे की संख्या की गिनती लौटाता है।
प्रारंभिक गिनती को 0 और सबसे छोटे सबएरे की लंबाई को temp=1 के रूप में लें।
फॉर लूप का उपयोग करके arr[] को ट्रैवर्स करें, यदि arr[i + 1] <= arr[i] तो temp बढ़ाएं क्योंकि सबएरे गैर-बढ़ता है।
अन्यथा ((temp + 1) * temp) / 2 को लंबाई temp के सबएरे के सबएरे की संख्या के लिए गिनती में जोड़ें जो गैर-बढ़ता है।
नए सबएरे के लिए temp=1 सेट करें।
सभी लूप के अंत में, यदि लंबाई temp>1 फिर से ((temp + 1) * temp) / 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
