|arr[i] – arr[j] - + |i – j| এর সর্বোচ্চ মান C++ এ

এই সমস্যায়, আমাদের n পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যা |arr[i]-arr[j]| এর সর্বোচ্চ মান খুঁজে পাবে + |i-j|.

সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,

ইনপুট − অ্যারে ={4, 1, 2}

আউটপুট − 4

ব্যাখ্যা −

|arr[0] - arr[1]|+|0-1| = |4-1| + |-1| = 3+1 = 4
|arr[0] - arr[2]|+|0-2| = |4-2| + |-2| = 2+2 = 4
|arr[1] - arr[2 ]|+|1-2| = |1-2| + |1-2| = 1+1 = 2

এই সমস্যা সমাধানের জন্য, একটি সহজ পদ্ধতি ব্যবহার করা হবে ব্রুট ফোর্স পদ্ধতি যা দুটি লুপ ব্যবহার করবে এবং সর্বাধিক পার্থক্য খুঁজে পাবে।

কিন্তু একটি দক্ষ পন্থা হবে পরম ফাংশনের বৈশিষ্ট্যগুলি ব্যবহার করে,

আসুন সমীকরণটি ডিকোড করি এবং সমাধানটি সন্ধান করি,

arr[i] - arr[j] + i - j = (arr[i] + i) - (arr[j] + j)
arr[i] - arr[j] - i + j = (arr[i] - i) - (arr[j] - j)
-arr[i] + arr[j] + i - j = -{(arr[i]-i) -(arr[j]-j)}
-arr[i] + arr[j] - i + j = -{(arr[i]+i) - (arr[j]+j)}

প্রথম এবং সামনে একই এবং দ্বিতীয় এবং চতুর্থ একই। এটি ব্যবহার করে আমরা দুটি অ্যারে তৈরি করব যা arr[i]+- i.

array1 arr[i] + i

array2 arr[i] - i

সুতরাং, আমরা সর্বাধিক দুটি মান খুঁজে পাব যেগুলি হল

সর্বোচ্চ ((সর্বোচ্চ(অ্যারে১)-মিন(অ্যারে১)), (সর্বোচ্চ(অ্যারে২)-মিন(অ্যারে২)))

উদাহরণ

আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,

#include<iostream>
using namespace std;
int maxDiff(int arr[], int n) {
   int ans = 0;
   for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
         ans = max(ans, abs(arr[i] - arr[j]) + abs(i - j));
   return ans;
}
int main() {
   int array[] = { 5, 7, 1, 2 };
   int n = sizeof(array) / sizeof(array[0]);
   cout<<"The maximum value of |arr[i] - arr[j]| + |i-j| is "<<maxDiff(array, n);
   return 0;
}

আউটপুট

The maximum value of |arr[i] - arr[j]| + |i-j| is 7