টাস্ক হলো একটি অ্যারে arr[]-কে K সংখ্যক কনসিকিউটিভ সাব-অ্যারে-এ ভাগ করে, সাব-অ্যারেগুলোর মিনিমাম মানগুলোর মধ্যে সর্বোচ্চ মান বের করা।
ইনপুট
arr[] = {2, 8, 4, 3, 9, 1, 5}, K=3
আউটপুট
9
ব্যাখ্যা − ৩টি কনসিকিউটিভ সাব-অ্যারে: {2,8,4,3}, {9}, {1,5}। মিনিমাম মানগুলো: ২, ৯, ১। সর্বোচ্চ: ৯।
ইনপুট
arr[] = {8, 4, 1, 9, 11}, K=1
আউটপুট
11
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- টাস্কটিকে ৩ কেসে ভাগ করা যায়: K=1, K=2, K>=3।
- K=1: সাব-অ্যারে হলো পুরো অ্যারে, তাই অ্যারের মিনিমাম মানই আউটপুট।
- K=2: কঠিন কেস। প্রিফিক্স এবং সাফিক্স মিনিমাম অ্যারে বানানো লাগে। প্রতিটি পজিশনে
MaxValue = max(MaxValue, max(prefixMin[i], suffixMin[i+1]))ক্যালকুলেট করুন। - K>=3: সর্বোচ্চ মানই আউটপুট (কারণ আমরা সর্বোচ্চ এলিমেন্টকে একা একটি সাব-অ্যারে হিসেবে রাখতে পারি)।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int Max(const int* arr, int size, int K) {
int Max = INT_MIN;
int Min = INT_MAX;
for (int i = 0; i < size; i++) {
Min = min(Min, arr[i]);
Max = max(Max, arr[i]);
}
if (K == 1) return Min;
else if (K >= 3) return Max;
else {
// K == 2
vector Left(size), Right(size);
Left[0] = arr[0];
Right[size-1] = arr[size-1];
for (int i = 1; i < size; i++)
Left[i] = min(Left[i-1], arr[i]);
for (int i = size-2; i >= 0; i--)
Right[i] = min(Right[i+1], arr[i]);
int MaxValue = INT_MIN;
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
