একটি অ্যারে arr[] দেওয়া আছে যেটি পজিটিভ ইন্টিজার ধারণ করে। লক্ষ্য হলো কমপক্ষে দৈর্ঘ্য ১ বিশিষ্ট সেই সাবঅ্রেগুলোর সংখ্যা বের করা যারা নন-ইনক্রিজিং (non-increasing)। যদি arr[] = {1,3,2} হয় তবে সাবঅ্রেগুলো হবে: {1}, {2}, {3}, {3,2}। কাউন্ট = ৪।
ইনপুট
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}
প্রোগ্রামে ব্যবহৃত পদ্ধতি:
এই পদ্ধতিতে আমরা এই fakt ব্যবহার করি যে যদি arr[]-এর ইন্ডেক্স i এবং j এর মধ্যে এলিমেন্টগুলো নন-ইনক্রিজিং না হয় তবে i থেকে j+1, j+2... i+j+n-1 পর্যন্ত কখনো নন-ইনক্রিজিং হবena। তাই সাবঅ্রের দৈর্ঘ্য বাড়িয়ে চলা হয় যতক্ষণ নন-ইনক্রিজিং থাকে। যদি কোনো ছোট এলিমেন্ট পাওয়া যায় arr[j] < arr[j-1] তবে len*(len+1)/2 (দৈর্ঘ্য len বিশিষ্ট নন-ইনক্রিজিং সাবঅ্রের সাবঅ্রে সংখ্যা) কাউন্টে যোগ করে দৈর্ঘ্য ১ রিসেট করা হয়।
- ইন্টিজার অ্যারে
arr[]নেওয়া হয়। subarrays(int arr[], int size)ফাংশন অ্যারে এবং সাইজ নিয়ে নন-ইনক্রিজিং সাবঅ্রে কাউন্ট রিটার্ন করে।- ইনিশিয়াল কাউন্ট ০ এবং ছোট সাবঅ্রের দৈর্ঘ্য
temp=1। - ফর লুপে
arr[i+1] <= arr[i]হলেtemp++(সাবঅ্রে নন-ইনক্রিজিং)। - অন্যথায়
(temp+1)*temp/2কাউন্টে যোগ করেtemp=1রিসেট। - সব লুপ শেষে যদি
temp>1হয় তবে আবার(temp+1)*temp/2যোগ করা হয় শেষ সাবঅ্রের জন্য। countরিটার্ন।
উদাহরণ
#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 of number of non-increasing subarrays are: 7
