ধনাত্মক পূর্ণসংখ্যা ধারণকারী একটি অ্যারে 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