প্রদত্ত কাজটি হল একটি অ্যারে অ্যারে[] কে পরপর সাব-অ্যারেতে ভাগ করা এবং K ধারাবাহিক সাব-srrayগুলির সর্বনিম্ন মধ্যে সর্বাধিক সম্ভাব্য সর্বাধিক মান খুঁজে বের করা।
ইনপুট
arr[]={2,8,4,3,9,1,5}, K=3 আউটপুট
9
ব্যাখ্যা − 3টি পরপর সাব অ্যারে তৈরি করা যেতে পারে:{2, 8, 4, 3}, {9}, এবং {1, 5}
এই সমস্ত অ্যারেগুলির মধ্যে সর্বনিম্ন মানগুলি হল:(2, 9, 1)
এই তিনটির মধ্যে সর্বাধিক মান হল 9৷
৷ইনপুট
arr[] = { 8, 4, 1, 9, 11}, K=1 আউটপুট
11
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
আমরা যদি কাজটি দেখি, এটিকে 3টি ক্ষেত্রে ভাগ করা যায় - যখন K=1, k=2 এবং k>=3।
-
কেস 1 − K=1
যখন k=1 সাব-অ্যারে নিজেই অ্যারের সমান হয় এবং তাই অ্যারের সর্বনিম্ন মান হবে আউটপুট।
-
কেস 2 − K=2
এটি একটি কঠিন মামলা. এই ক্ষেত্রে আমাদের দুটি অ্যারে তৈরি করতে হবে যাতে উপসর্গ এবং প্রত্যয় ন্যূনতম থাকবে কারণ অ্যারেটিকে কেবল 2টি অংশে ভাগ করা যায়। তারপর অ্যারের প্রতিটি উপাদানের জন্য আমাদের তা করতে হবে −
MaxValue =max(MaxValue, max(i-এ উপসর্গ সর্বনিম্ন মান, i+1-এ প্রত্যয় সর্বাধিক মান)
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
/* Function to find the maximum possible value
of the maximum of minimum of K sub-arrays*/
int Max(const int* arr, int size, int K){
dint Max;
int Min;
//Obtain maximum and minimum
for (int i = 0; i < size; i++){
Min = min(Min, arr[i]);
Max = max(Max, arr[i]);
}
//When K=1, return minimum value
if (K == 1){
return Min;
}
//When K>=3, return maximum value
else if (K >= 3){
return Max;
}
/*When K=2 then make prefix and suffix minimums*/
else{
// Arrays to store prefix and suffix minimums
int Left[size], Right[size];
Left[0] = arr[0];
Right[size - 1] = arr[size - 1];
// Prefix minimum
for (int i = 1; i < size; i++){
Left[i] = min(Left[i - 1], arr[i]);
}
// Suffix minimum
for (int i = size - 2; i >= 0; i--){
Right[i] = min(Right[i + 1], arr[i]);
}
int MaxValue=INT_MIN;
// Get the maximum possible value
for (int i = 0; i < size - 1; i++){
MaxValue = max(MaxValue, max(Left[i], Right[i + 1]));
}
return MaxValue;
}
}
int main(){
int arr[] = {9,4,12,5,6,11};
int size = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout<<"Maximize the maximum among minimum of K consecutive sub-arrays is: "<<Max(arr, size, K);
return 0;
} আউটপুট
আমরা উপরের কোডটি চালালে আমরা নিম্নলিখিত আউটপুট পাব −
Maximize the maximum among minimum of K consecutive sub-arrays is: 11
