এই সমস্যা, আমরা একটি অ্যারে দেওয়া হয়. আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যাতে C++-এ যেকোন পারমুটেশনের সর্বোচ্চ পার্থক্য নির্ণয় করা।
সমস্যা বর্ণনা
আমরা প্রদত্ত অ্যারের উপাদানগুলির সমস্ত স্থানান্তর খুঁজে পাব। এবং তারপর অ্যারের সন্নিহিত উপাদানগুলির পরম পার্থক্যের যোগফল খুঁজে বের করা। সবশেষে আমরা সর্বোচ্চ সব রাশি ফেরত দেব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {9, 1, 6, 3} আউটপুট
17
ব্যাখ্যা
All permutations of the array with sum of absolute difference of adjacent elements.
{9, 1, 6, 3},
sum= |9-1| + |1-6| + |6-3| + |3-9| = 8+5+3+6 = 16
{9, 1, 3, 6},
sum= |9-1| + |1-3| + |3-6| + |6- 9| = 8+2+3+3 = 16
{9, 6, 1, 3},
sum= |9-6| + |6-1| + |1-3| + |3 - 9| = 3+5+2+6 = 16
{9, 6, 3, 1},
sum= |9-6| + |6-3| + |3-1| + |1 - 9| = 3+3+2+8 = 16
{9, 3, 1, 6},
sum= |9-3| + |3-1| + |1-6| + |6- 9| = 6+2+5+3 = 16
{9, 3, 6, 1},
sum= |9-3| + |3-6| + |6-1| + |1- 9| = 6+3+5+8 = 22
{1, 9, 6, 3},
sum= |1-9| + |9-6| + |6-3| + |3-1| = 8+3+3+2 = 16
{1, 9, 3, 6},
sum= |1-9| + |9-3| + |3-6| +
|6 - 1| = 8+6+3+5 = 22
{1, 6, 9, 3},
sum= |1-6| + |6-9| + |9-3| + |3 - 1| = 5+3+6+2 = 16
{1, 6, 3, 9},
sum= |1-6| + |6-3| + |3-9| + |9-1| = 5+3+6+8 = 22
{1, 3, 9, 6},
sum= |1-3| + |3-9| + |9-6| + |6-1| = 2+6+3+5 = 16
{1, 3, 6, 9},
sum= |1-3| + |3-6| + |6-9| + |9 - 1| = 2+3+3+8 = 16
.. এবং 6 এবং 3 গ্রহণকারী সমস্ত পারমুটেশন হল প্রারম্ভিক সংখ্যা।
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান সর্বাধিক সমাধানের সর্বোত্তম উপায় খুঁজে বের করার মাধ্যমে পাওয়া যেতে পারে। এবং সমাধানটি সর্বাধিক করার জন্য, আমাদের অ্যারের জন্য সমস্ত সর্বোচ্চ পরম পার্থক্য খুঁজে বের করতে হবে। এবং এটি | ক্ষুদ্রতম - সর্বোচ্চ
অ্যালগরিদম
ধাপ 1 - অ্যারে সাজান।
ধাপ 2 − এখন, সবচেয়ে ছোট সংখ্যা এবং সাজানো অ্যারের সবচেয়ে বড় সংখ্যার মধ্যে পরম পার্থক্য যোগ করে ম্যাক্সসাম গণনা করা হয়।
ধাপ 3 − শেষে, maxSum ফেরত দিন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <bits/stdc++.h>
using namespace std;
int calcMaxSumAbsDiff(int arr[], int N){
int maxSumArray[N];
int j = 0, maxSum = 0;
sort(arr, arr + N);
for (int i = 0; i < (N/2); ++i){
maxSumArray[j] = arr[i];
maxSumArray[j+1] = arr[N - i - 1];
j += 2;
}
if (N % 2 != 0)
maxSumArray[j] = arr[N/2];
for (int i = 0; i < N - 1; i++){
maxSum += abs(maxSumArray[i] - maxSumArray[i + 1]);
}
maxSum += abs(maxSumArray[N - 1] - maxSumArray[0]);
return maxSum;
}
int main(){
int arr[] = {9, 1, 6, 3};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum of absolute difference of any permutation is "<<calcMaxSumAbsDiff(arr, N);
} আউটপুট
The maximum sum of absolute difference of any permutation is 22
