এই সমস্যায়, আমাদেরকে N পূর্ণসংখ্যার মানগুলির উপর জোর দিয়ে একটি অ্যারে অ্যারে দেওয়া হয়েছে৷ আমাদের কাজ হল অ্যারায়ারের []-এ abs(i – j) * min(arr[i], arr[j]) এর সর্বাধিক মান খুঁজে বের করা।
সমস্যা বর্ণনা − আমাদের দুটি উপাদানের সর্বনিম্ন মানের সর্বোচ্চ পণ্যের মান এবং তাদের সূচকগুলির মধ্যে পরম পার্থক্য খুঁজে বের করতে হবে। যেমন i এবং j দুটি মানের জন্য, আমাদের maximize করতে হবে, abs(i - j) * min(arr[i] , arr[j])।
ইনপুট
arr[] = {5, 7, 3, 6, 4} আউটপুট
16
ব্যাখ্যা
The maximum value is 16, between index 0 and 4 => abs(0 - 4)*min(arr[0], arr[4]) => 4*min(5, 4) => 4*4 = 16
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল নেস্টেড লুপ ব্যবহার করা। আমরা টুলুপ নেব এবং i এবং j এর প্রতিটি জোড়ার মান গণনা করব। এবং তারপরে পাওয়া সমস্ত মানগুলির সর্বাধিক ফেরত দিন৷
এই পদ্ধতিটি ভাল কিন্তু O(n 2 অর্ডারের একটি সময় জটিল )।
সমস্যার একটি কার্যকর সমাধান হল অ্যারের শেষ থেকে অন্যটির শুরু থেকে দুটি পুনরাবৃত্তিকারী মান ব্যবহার করা। পুনরাবৃত্তিকারীর প্রতিটি মানের জন্য আমরা প্রয়োজনীয় মান খুঁজে বের করব এবং তাদের তুলনা করব এবং সর্বাধিক inmaxVal ভেরিয়েবল সংরক্ষণ করব। আমরা এটি করব যতক্ষণ না উভয় পুনরাবৃত্তিকারী একে অপরকে অতিক্রম করে এবং শেষে maxVal ফেরত দেয়।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
