বিবরণ
(2 * n - 1) সংখ্যক ইন্টিজারের একটি অ্যারে আছে। আমরা অ্যারেতে ঠিক n সংখ্যক উপাদানের চিহ্ন পরিবর্তন করতে পারি। অর্থাৎ, আমরা ঠিক n সংখ্যক অ্যারে উপাদান বেছে নিতে পারি এবং তাদের প্রতিটিকে -1 দিয়ে গুণ করতে পারি। অ্যারের সর্বোচ্চ যোগফল বের করুন।
উদাহরণ
যদি ইনপুট অ্যারে হয় {-2, 100, -3} তবে আমরা -2 এবং -3-এর চিহ্ন পরিবর্তন করে সর্বোচ্চ মান পেতে পারি। চিহ্ন পরিবর্তন করার পর অ্যারে হয়:
{2, 100, 3} এবং এই অ্যারের সর্বোচ্চ যোগফল হল ১০৫।
অ্যালগরিদম
- নেগেটিভ সংখ্যাগুলোর গণনা করুন।
- সংখ্যাগুলোর অ্যাবসোলিউট মান নিয়ে অ্যারের যোগফল বের করুন।
- সংখ্যাগুলোর অ্যাবসোলিউট মান নিয়ে অ্যারের ন্যূনতম সংখ্যা বের করুন।
- চেক করুন যে নেগেটিভ সংখ্যার সংখ্যা বিজোড় এবং 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
