इस समस्या में, हमें एक सरणी दी जाती है। हमारा काम 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 - अंत में, अधिकतम राशि लौटाएं।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#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