এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে যেটিতে 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