এই সমস্যায়, আমাদের একটি অ্যারে দেওয়া আছে। আমাদের কাজ হল সি++-এ যেকোনো পারমিউটেশনে পরম পার্থক্যের সর্বোচ্চ যোগফল বের করার একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
আমরা দেয়া অ্যারেতে উপাদানগুলোর সব পারমিউটেশন বের করব। এবং তারপর অ্যারেতে সন্নিহিত উপাদানগুলোর পরম পার্থক্যের যোগফল বের করব। শেষে সব যোগফলের মধ্যে সর্বোচ্চটি ফেরত দেব।
উদাহরণ দিয়ে বুঝতে চেষ্টা করি,
ইনপুট
arr[] = {9, 1, 6, 3}
আউটপুট
17
ব্যাখ্যা
অ্যারেতে সব পারমিউটেশন এবং সন্নিহিত উপাদানগুলোর পরম পার্থক্যের যোগফল। {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 দিয়ে শুরু হওয়া সব পারমিউটেশন।
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল সমাধানকে সর্বোচ্চ করার সেরা উপায় খুঁজে বের করা। এবং সমাধান সর্বোচ্চ করার জন্য, আমাদের অ্যারেতে সবচেয়ে বড় পরম পার্থক্য খুঁজে বের করতে হবে। এবং এটি ছোট বড়ের পরম পার্থক্য |smallest - highest| ব্যবহার করে বের করা যায়।
অ্যালগরিদম
ধাপ ১ − অ্যারেটি সোর্ট করুন।
ধাপ ২ − এখন, maxSum হল সোর্ট করা অ্যারেতে সবচেয়ে ছোট এবং সবচেয়ে বড় সংখ্যার পরম পার্থক্য যোগ করে বের করা।
ধাপ ৩ − শেষে, 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
