सरणी में नकारात्मक संख्याएं भी हो सकती हैं। जोड़े बनाकर गुणा करने पर अधिकतम योग प्राप्त करें। मॉड्यूलो 10^9+7 लें।
रणनीति: सरणी को सॉर्ट करें। नकारात्मक संख्याओं को जोड़े में (सबसे छोटे से) गुणा करें, धनात्मक को जोड़े में (सबसे बड़े से) गुणा करें। यदि एक नकारात्मक और एक धनात्मक बचे तो उन्हें गुणा करें।
उदाहरण: {-1, 9, 4, 5, -4, 7} → अधिकतम योग 87।
C++ कार्यान्वयन
#include <bits/stdc++.h>
#define Mod 1000000007
using namespace std;
long long int findSum(int arr[], int n) {
long long int sum = 0;
sort(arr, arr + n);
int i = 0;
while (i < n && arr[i] < 0) {
if (i != n - 1 && arr[i + 1] <= 0) {
sum = (sum + (1LL * arr[i] * arr[i + 1]) % Mod) % Mod;
i += 2;
} else break;
}
int j = n - 1;
while (j >= 0 && arr[j] > 0) {
if (j != 0 && arr[j - 1] > 0) {
sum = (sum + (1LL * arr[j] * arr[j - 1]) % Mod) % Mod;
j -= 2;
} else break;
}
if (j > i) sum = (sum + (1LL * arr[i] * arr[j]) % Mod) % Mod;
else if (i == j) sum = (sum + arr[i]) % Mod;
return sum;
}
int main() {
int arr[] = {-1, 9, 4, 5, -4, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSum(arr, n);
return 0;
}
आउटपुट
87
