इस समस्या में, हमें एक सरणी arr [] दिया जाता है जिसमें n पूर्णांक मान (ऋणात्मक मान अनुमत) होते हैं। हमारा काम नकारात्मक अनुमत सरणी में जोड़ीवार उत्पादों की अधिकतम राशि खोजने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण - हमें सरणी के तत्वों का उपयोग करके जोड़े बनाने की जरूरत है ताकि जोड़े के तत्वों के उत्पाद का योग अधिकतम हो।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {−5, 2, 3, 7, −1, 1, −3, 12} आउटपुट
104
स्पष्टीकरण
The pairs to be considered: (−5, −3), (2, 3), (−1, 1), (7, 12) Sum of product = (−5 * −3) + (2 * 3) + (−1 * 1) + (7 * 12) = 15 + 6 − 1 + 84 = 104.
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हम जोड़े इस तरह से खोजेंगे कि उनके उत्पादों का योग अधिकतम हो। योग को अधिकतम करने के लिए, हमें समान युग्म मानों को एक साथ जोड़ना होगा। और इस जोड़ी को आसान बनाने के लिए, हमें सरणी को सॉर्ट करना होगा और फिर नकारात्मक और सकारात्मक को जोड़ना होगा। फिर ज्ञात कीजिए कि युग्म में एक धनात्मक या ऋणात्मक या दोनों मान मौजूद हैं या नहीं। यदि कोई धनात्मक/ऋणात्मक मान शेष है, तो उसे युग्म में जोड़ें और यदि एक ऋणात्मक और एक धनात्मक मौजूद है तो उनका गुणनफल जोड़ें।
एल्गोरिदम
आरंभ करें -
maxSum = 0.
चरण 1 -
Sort the array arr[].
चरण 2 -
Loop for all negative values of the array. Make pairs, and add their product to maxSum.
चरण 3 -
Loop for all positive values of the array. Make pairs, and add their product to maxSum.
चरण 4 -
At last check the remaining values.
चरण 4.1 -
If one positive value remains, add it to maxSum.
चरण 4.1 -
If one negative value remains, add it to maxSum.
चरण 4.1 -
If one positive value and one negative value remains, add their product to maxSum.
चरण 5 -
Return maxSum.
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <bits/stdc++.h>
using namespace std;
long calcSumPairProd(int arr[], int n) {
long maxSum = 0;
sort(arr, arr + n);
int i = 0, j = (n − 1);
while (i < n && arr[i] < 0) {
if (i != n − 1 && arr[i + 1] <= 0) {
maxSum = (maxSum + (arr[i] * arr[i + 1]) );
i += 2;
}
else
break;
}
while (j >= 0 && arr[j] > 0) {
if (j != 0 && arr[j − 1] > 0) {
maxSum = (maxSum + (arr[j] * arr[j − 1]) );
j −= 2;
}
else
break;
}
if (j > i)
maxSum = (maxSum + (arr[i] * arr[j]) );
else if (i == j)
maxSum = (maxSum + arr[i]);
return maxSum;
}
int main() {
int arr[] = { −5, 2, 3, 7, −1, 1, −3, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum of pairwise product in an array is "<<calcSumPairProd(arr, n);
return 0;
} आउटपुट
The maximum sum of pairwise product in an array is 104