সমস্যা বিবরণ
একটি পূর্ণসংখ্যা অ্যারে এবং একটি রেঞ্জ দেওয়া হয়েছে। আমাদের কাজ হল সেই রেঞ্জের সাবঅ্যারে পর্বত আকারে (প্রথম বেড়ে পরে কমে) আছে কিনা তা যাচাই করা।
উদাহরণ
ইনপুট: arr[] = {1, 4, 2, 5, 6, 7, 3, 0}, রেঞ্জ = [2, 7]
আউটপুট: Yes
ব্যাখ্যা: সাবঅ্যারে = {2, 5, 6, 7, 3, 0} — মান প্রথমে বেড়েছে, পরে কমেছে।
সমাধানের পদ্ধতি
প্রতিটি উপাদানের জন্য বাম ও ডান পাশে সর্বোচ্চ বেড়ে ও কমে যাওয়ার সূচক সংরক্ষণ করে রেঞ্জ যাচাই করা।
প্রোগ্রাম উদাহরণ
#include <iostream>
using namespace std;
void processArray(int arr[], int N, int left[], int right[]) {
left[0] = 0;
int inc = 0;
for (int i = 1; i < N; i++) {
if (arr[i] > arr[i-1]) inc = i;
left[i] = inc;
}
right[N-1] = N-1;
int dec = N-1;
for (int i = N-2; i >= 0; i--) {
if (arr[i] > arr[i+1]) dec = i;
right[i] = dec;
}
}
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, R = 2;
if (isMountainSubArray(arr, left, right, L, R))
cout << "সাবঅ্যারে পর্বত আকারে আছে";
else
cout << "সাবঅ্যারে পর্বত আকারে নেই";
return 0;
}
আউটপুট
সাবঅ্যারে পর্বত আকারে আছে
