এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে N সংখ্যক পূর্ণসংখ্যা থাকে। আমাদের কাজ হলো abs(i-j) * min(arr[i], arr[j]) এর সর্বোচ্চ মান খুঁজে বের করা।
সমস্যা বিবরণ
দুটি ভ্যালু i এবং j-এর জন্য, আমাদের(abs(i - j) * min(arr[i], arr[j])) নিকটস্থ মান সর্বোচ্চ করতে হবে।
উদাহরণ
ইনপুট
arr[] = {5, 7, 3, 6, 4}
আউটপুট
16
ব্যাখ্যা
সর্বোচ্চ মান ১৬, ইনডেক্স ০ এবং ৪-এর মধ্যে: abs(0 - 4) * min(arr[0], arr[4]) = 4 * min(5, 4) = 4 * 4 = 16
সমাধানের পদ্ধতি
একটি সহজ সমাধান হলো নেস্টেড লুপ ব্যবহার করা। দুটি লুপ নিয়ে i এবং j-এর সব জোড়ার জন্য মান বের করব এবং সর্বোচ্চ মান ফেরত দিব। কিন্তু এর টাইম কমপ্লেক্সিটি O(n²)।
একটি কার্যকর সমাধান হলো দুটি ইটারেটর ব্যবহার করা - একটি অ্যারের শুরু থেকে এবং অন্যটি শেষ থেকে। প্রতিটি ইটারেটর ভ্যালুর জন্য প্রয়োজনীয় মান বের করে তুলনা করব এবং সর্বোচ্চ মান maxVal-এ সংরক্ষণ করব। দুটি ইটারেটর একে অপর লাঙ্ঘন করতেই লুপ বন্ধ করে maxVal ফেরত দিব।
C++ প্রোগ্রাম উদাহরণ
#include<iostream>
using namespace std;
int calcMaxProdValue(int arr[], int n) {
int maxVal = -100;
int currentVal;
int start = 0, end = n-1;
while (start < end) {
if (arr[start] < arr[end]) {
currentVal = arr[start] * (end - start);
start++;
}
else {
currentVal = arr[end] * (end - start);
end--;
}
maxVal = max(maxVal, currentVal);
}
return maxVal;
}
int main(){
int arr[] = {5, 7, 3, 6, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum value of abs(i - j) * min(arr[i], arr[j]) in an array is " << calcMaxProdValue(arr,n);
return 0;
}
আউটপুট
The maximum value of abs(i - j) * min(arr[i], arr[j]) in an array is 16
