ধনাত্মক পূর্ণসংখ্যা ধারণকারী একটি অ্যারে 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
ব্যাখ্যা
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} নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
এই পদ্ধতিতে, আমরা এই সত্যটি ব্যবহার করব যে যদি সূচী i এবং j in arr[]-এর মধ্যে উপাদানগুলি অ-বৃদ্ধি না হয় তবে i থেকে j+1, i থেকে j+2….i থেকে j+n−1 সূচকগুলির মধ্যে উপাদানগুলি কখনই না বাড়তে পারে না তাই এই সাবয়ারের দৈর্ঘ্য বাড়াতে থাকুন যতক্ষণ না উপাদানগুলি বৃদ্ধি পাচ্ছে না। যদি কোনো কম উপাদান পাওয়া যায় arr[j]
একটি পূর্ণসংখ্যা অ্যারে arr[] নিন।
ফাংশন subarrays(int arr[], int size) অ্যারে এবং এর আকার নেয় এবং অ-বর্ধিত সাবয়ারের সংখ্যার গণনা প্রদান করে।
টেম্প=1 হিসাবে প্রাথমিক গণনা 0 এবং ক্ষুদ্রতম সাবয়ারের দৈর্ঘ্য নিন।
ট্রাভার্স arr[] লুপের জন্য ব্যবহার করে, যদি arr[i + 1] <=arr[i] হয় তাহলে সাবঅ্যারে অ-বর্ধমান হিসাবে তাপমাত্রা বৃদ্ধি করুন।
অন্যথায় (temp + 1) * temp) / 2 যোগ করুন সাবরেয়ের দৈর্ঘ্যের টেম্পের সাবব্রের সংখ্যা যা অ-বর্ধমান।
নতুন সাবয়ারের জন্য 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
