इस समस्या में, हमें एक सरणी arr[] दी गई है जिसमें n पूर्णांक मान हैं (ऋणात्मक मान अनुमत हैं)। हमारा कार्य एक प्रोग्राम बनाना है जो ऋणात्मक मानों के साथ सरणी में युग्मवार उत्पादों का अधिकतम योग ढूंढे।
समस्या विवरण
हमें सरणी के तत्वों का उपयोग करके युग्म बनाने हैं ताकि युग्मों के तत्वों के उत्पाद का योग अधिकतम हो।
उदाहरण
इनपुट
arr[] = {-5, 2, 3, 7, -1, 1, -3, 12}
आउटपुट
104
व्याख्या
विचार करने योग्य युग्म: (-5, -3), (2, 3), (-1, 1), (7, 12) उत्पाद का योग = (-5 * -3) + (2 * 3) + (-1 * 1) + (7 * 12) = 15 + 6 - 1 + 84 = 104।
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हम ऐसे युग्म ढूंढेंगे कि उनके उत्पादों का योग अधिकतम हो। योग को अधिकतम करने के लिए, हमें समान मान वाले मानों को एक साथ जोड़ना होगा। और इस युग्मन को आसान बनाने के लिए, हमें सरणी को क्रमबद्ध करना होगा और फिर ऋणात्मक और धनात्मक को जोड़ना होगा। फिर जांचें कि क्या एक धनात्मक या ऋणात्मक या दोनों मान युग्म में मौजूद हैं। यदि एक धनात्मक/ऋणात्मक मान शेष है तो उसे युग्म में जोड़ें और यदि एक ऋणात्मक और एक धनात्मक मौजूद हैं तो उनका उत्पाद जोड़ें।
एल्गोरिदम
आरंभीकरण -
maxSum = 0।
चरण 1 -
सरणी arr[] को क्रमबद्ध करें।
चरण 2 -
सरणी के सभी ऋणात्मक मानों के लिए लूप। युग्म बनाएं, और उनके उत्पाद को maxSum में जोड़ें।
चरण 3 -
सरणी के सभी धनात्मक मानों के लिए लूप। युग्म बनाएं, और उनके उत्पाद को maxSum में जोड़ें।
चरण 4 -
अंत में शेष मानों की जांच करें।
चरण 4.1 -
यदि एक धनात्मक मान शेष है, तो इसे maxSum में जोड़ें।
चरण 4.2 -
यदि एक ऋणात्मक मान शेष है, तो इसे maxSum में जोड़ें।
चरण 4.3 -
यदि एक धनात्मक और एक ऋणात्मक मान शेष है, तो उनके उत्पाद को maxSum में जोड़ें।
चरण 5 -
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
