বিবরণ
(2 * n – 1) পূর্ণসংখ্যার একটি অ্যারে রয়েছে। আমরা অ্যারের ঠিক n উপাদানের চিহ্ন পরিবর্তন করতে পারি। অন্য কথায়, আমরা ঠিক n অ্যারে উপাদান নির্বাচন করতে পারি এবং তাদের প্রতিটিকে -1 দ্বারা গুণ করতে পারি। অ্যারের সর্বোচ্চ যোগফল খুঁজুন।
উদাহরণ
যদি ইনপুট অ্যারে হয় {-2, 100, -3} তাহলে আমরা -2 এবং -3-এর সর্বাধিক পরিবর্তনশীল চিহ্ন পেতে পারি। সাইন অ্যারে পরিবর্তন করার পর −
হয়ে যায়{2, 100, 3} এবং এই অ্যারের সর্বোচ্চ যোগফল হল 105৷
অ্যালগরিদম
- নেতিবাচক সংখ্যা গণনা করুন
- সংখ্যার পরম মান নিয়ে অ্যারের যোগফল গণনা করুন।
- সংখ্যার পরম মান গ্রহণ করে অ্যারের সর্বনিম্ন সংখ্যা খুঁজুন
- না আছে কিনা চেক করুন। ঋণাত্মক সংখ্যার বিজোড় এবং n-এর মান জোড় হলে যোগফল থেকে m দুইগুণ বিয়োগ করা হয় এবং এটি অ্যারের সর্বোচ্চ যোগফল হবে, যোগফলের মান হবে অ্যারের সর্বোচ্চ যোগফল
- উপরের ধাপগুলি (2 * n – 1) বার পুনরাবৃত্তি করুন
উদাহরণ
আসুন এখন একটি উদাহরণ দেখি -
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
int negtiveCnt = 0;
int sum = 0;
int m = INT_MAX;
for (int i = 0; i < 2 * n - 1; ++i) {
if (arr[i] < 0) {
++negtiveCnt;
}
sum = sum + abs(arr[i]);
m = min(m, abs(arr[i]));
}
if (negtiveCnt % 2 && n % 2 == 0) {
sum = sum - 2 * m;
return sum;
}
return sum;
}
int main() {
int arr[] = {-2, 100, -3};
int n = 2;
cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
return 0;
} আউটপুট
Maximum sum = 105
