সমস্যা বিবরণ
একটি অ্যারে (নেগেটিভ সংখ্যা থাকতে পারে) দেওয়া থাকলে, এলিমেন্টগুলো জোড়া বানিয়ে গুণফল নিন এবং তাদের সম সর্বোচ্চ করুন। অদ্দা এলিমেন্ট থাকলে সেটি সরাসরি যোগ করুন।
সমাধানের পদ্ধতি
- অ্যারে সর্ট করুন।
- নেগেটিভ সংখ্যাগুলো জোড়া বানান (সবচেয়ে ছোট দুটি নেগেটিভ গুণ করলে পজেটিভ হয়)۔
- পজেটিভ সংখ্যাগুলো জোড়া বানান (সবচেয়ে বড় দুটি গুণ করুন)۔
- যদি একটা নেগেটিভ ও একটা পজেটিভ বাকি থাকে, সেগুলো গুণ করুন।
- মডুলো 1000000007 নিন।
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 + (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 + (arr[j] * arr[j - 1]) % Mod) % Mod;
j -= 2;
} else break;
}
if (j > i)
sum = (sum + (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
ব্যাখ্যা
সর্টেড: [-4, -1, 4, 5, 7, 9]
নেগেটিভ জোড়া: (-4)×(-1) = 4
পজেটিভ জোড়া: 9×7 = 63, 5×4 = 20
মোট = 4 + 63 + 20 = 87
জটিলতা
- সময়: O(n log n)
- স্থান: O(1)
