এই সমস্যায়, আমাদেরকে পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়েছে arr[] এবং একটি পরিসর। আমাদের কাজ হল একটি সাব্যারে পর্বত আকারে আছে কিনা তা খুঁজে বের করা .
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : arr[] = {1, 4, 2, 5, 6, 7, 3, 0}, range = [2, 7]
Output : Yes ব্যাখ্যা −
Subarray of range = {2, 5, 6, 7, 3, 0}
The values first increase and then decrease. সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল অতিরিক্ত অ্যারে ব্যবহার করে। আমরা শেষ উপাদানটির সূচী খুঁজে পাব যা অ্যারের প্রতিটি উপাদানের জন্য বাড়ছে এবং মান হ্রাস করার জন্য একই কাজ করবে। তারপর নির্দিষ্ট সময়ের মধ্যে পর্বতটি পরীক্ষা করুন৷
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int processArray(int arr[], int N, int left[], int right[]){
left[0] = 0;
int increasingValR = 0;
for (int i = 1; i < N; i++){
if (arr[i] > arr[i - 1])
increasingValR = i;
left[i] = increasingValR;
}
right[N - 1] = N - 1;
int decreasingValL = N - 1;
for (int i = N - 2; i >= 0; i--){
if (arr[i] > arr[i + 1])
decreasingValL = i;
right[i] = decreasingValL;
}
}
bool isMountainSubArray(int arr[], int left[], int right[], int L, int R){
return (right[L] >= left[R]);
}
int main(){
int arr[] = {2, 3, 2, 4, 4, 6, 3, 2};
int N = sizeof(arr) / sizeof(int);
int left[N], right[N];
processArray(arr, N, left, right);
int L = 0;
int R = 2;
if (isMountainSubArray(arr, left, right, L, R))
cout<<"The subarray is in mountain form";
else
cout<<"The subarray is not in mountain form";
return 0;
} আউটপুট
The subarray is in mountain form
