C++ में किसी भी क्रमपरिवर्तन के निरपेक्ष अंतर का अधिकतम योग

समस्या विवरण

इस समस्या में, हमें एक सरणी दी गई है। हमारा कार्य C++ में किसी भी क्रमपरिवर्तन के निरपेक्ष अंतर का अधिकतम योग खोजने के लिए एक प्रोग्राम बनाना है।

हम दिए गए सरणी के तत्वों के सभी क्रमपरिवर्तन ढूंढेंगे। और फिर सरणी के आसन्न तत्वों के निरपेक्ष अंतर का योग ढूंढेंगे। अंत में हम सभी योगों में से अधिकतम लौटाएंगे।

उदाहरण

इनपुट

arr[] = {9, 1, 6, 3}

आउटपुट

व्याख्या

सरणी के सभी क्रमपरिवर्तन जिनमें आसन्न तत्वों के निरपेक्ष अंतर का योग है।
{9, 1, 6, 3}, योग = |9-1| + |1-6| + |6-3| + |3-9| = 8+5+3+6 = 16
{9, 1, 3, 6}, योग = |9-1| + |1-3| + |3-6| + |6-9| = 8+2+3+3 = 16
{9, 6, 1, 3}, योग = |9-6| + |6-1| + |1-3| + |3-9| = 3+5+2+6 = 16
{9, 6, 3, 1}, योग = |9-6| + |6-3| + |3-1| + |1-9| = 3+3+2+8 = 16
{9, 3, 1, 6}, योग = |9-3| + |3-1| + |1-6| + |6-9| = 6+2+5+3 = 16
{9, 3, 6, 1}, योग = |9-3| + |3-6| + |6-1| + |1-9| = 6+3+5+8 = 22
{1, 9, 6, 3}, योग = |1-9| + |9-6| + |6-3| + |3-1| = 8+3+3+2 = 16
{1, 9, 3, 6}, योग = |1-9| + |9-3| + |3-6| + |6-1| = 8+6+3+5 = 22
{1, 6, 9, 3}, योग = |1-6| + |6-9| + |9-3| + |3-1| = 5+3+6+2 = 16
{1, 6, 3, 9}, योग = |1-6| + |6-3| + |3-9| + |9-1| = 5+3+6+8 = 22
{1, 3, 9, 6}, योग = |1-3| + |3-9| + |9-6| + |6-1| = 2+6+3+5 = 16
{1, 3, 6, 9}, योग = |1-3| + |3-6| + |6-9| + |9-1| = 2+3+3+8 = 16
...

और 6 और 3 से शुरू होने वाले सभी क्रमपरिवर्तन।

समाधान दृष्टिकोण

समस्या का एक सरल समाधान समाधान को अधिकतम करने के सर्वोत्तम तरीके को ढूंढकर पाया जा सकता है। और समाधान को अधिकतम करने के लिए, हमें सरणी के लिए सभी अधिकतम निरपेक्ष अंतर ढूंढने होंगे। और यह सरणी के |सबसे छोटा - सबसे बड़ा| के निरपेक्ष अंतर का उपयोग करके पाया जा सकता है।

एल्गोरिदम

चरण 1 - सरणी को क्रमबद्ध करें।

चरण 2 - अब, maxsum की गणना क्रमबद्ध सरणी की सबसे छोटी संख्या और सबसे बड़ी संख्या के बीच निरपेक्ष अंतर को जोड़कर की जाती है।

चरण 3 - अंत में, maxSum वापस करें।

C++ कार्यान्वयन

#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