C++ प्रोग्राम में अधिकतम वजन अंतर

समस्या विवरण

इस समस्या में, हमें एक ऐरे arr[] और एक संख्या M दी गई है। हमारा कार्य C++ में अधिकतम वजन अंतर की गणना करने का प्रोग्राम बनाना है।

समस्या विवरण

हम ऐरे से M तत्व ढूंढेंगे जैसे कि उनके योग और शेष तत्वों के योग के बीच निरपेक्ष अंतर अधिकतम हो।

उदाहरण

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

आउटपुट

15

व्याख्या

हम 4, 6, 9 पर विचार करेंगे। योग 19 है। शेष संख्याओं के योग के साथ निरपेक्ष अंतर है

|19 - 4| = 15

हल करने का दृष्टिकोण

समस्या का एक सरल हल ऐरे के सभी सबसीक्वेंस ढूंढना, सबऐरे के तत्वों का योग और शेष का योग ढूंढना, और अधिकतम अंतर वापस करना है।

एक अधिक कुशल हल इस तथ्य का उपयोग करके पाया जाता है कि अधिकतम वजन अंतर यानी तत्वों के योग और शेष का अंतर अधिकतम होता है यदि हम सबसीक्वेंस के लिए m अधिकतम तत्व या m न्यूनतम तत्व पर विचार करते हैं।

तो, हम m सबसे बड़े तत्वों और शेष ऐरे के सबसीक्वेंस के लिए अधिकतम योग अंतर की जांच करेंगे या m सबसे छोटे तत्वों और शेष ऐरे के सबसीक्वेंस के लिए। और दोनों में से अधिकतम वापस करेंगे।

एल्गोरिदम

1. आरंभीकरण - maxSum, maxSumDiff, minSumDiff
2. चरण 1 - ऐरे को अवरोही क्रम में सॉर्ट करें।
3. चरण 2 - i -> 0 से n तक लूप
   • चरण 2.1 - यदि (i < m) -> maxSumDiff += arr[i]
   • चरण 2.2 - अन्यथा -> maxSumDiff -= arr[i]
4. चरण 3 - i -> n से 0 तक लूप
   • चरण 3.1 - यदि (i > m) -> minSumDiff += arr[i]
   • चरण 3.2 - अन्यथा -> minSumDiff -= arr[i]
5. चरण 4 - यदि maxSumDiff > minSumDiff -> maxSum = maxSumDiff
6. चरण 5 - यदि maxSumDiff < minSumDiff -> maxSum = minSumDiff
7. चरण 6 - maxSum वापस करें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int maxWeightDifference(int arr[], int N, int M) {
    int maxabsDiff = -1000;
    sort(arr, arr + N);
    int sumMin = 0, sumMax = 0, arrSum = 0;
    for (int i = 0; i < N; i++) {
        arrSum += arr[i];
        if (i < M)
            sumMin += arr[i];
        if (i >= (N - M))
            sumMax += arr[i];
    }
    maxabsDiff = max(abs(sumMax - (arrSum - sumMax)), abs(sumMin - (arrSum - sumMin)));
    return maxabsDiff;
}

int main() {
    int arr[] = {3, 1, 6, 9, 4};
    int M = 3;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum weight difference is " << maxWeightDifference(arr, N, M);
    return 0;
}

आउटपुट

The maximum weight difference is 15