সমস্যা বিবরণ
আকার n-এর একটি অ্যারে এবং একটি সংখ্যা k দেওয়া আছে। আমাদের অ্যারেটি k বার মডিফাই করতে হবে।
মডিফাই মানে প্রতিটি অপারেশনে আমরা যেকোনো একটি অ্যারে উপাদান arr[i]-কে 네가েট করে অর্থাৎ arr[i] = -arr[i] দিয়ে রিপ্লেস করতে পারি। কাজ হল এই অপারেশনটি এমনভাবে করা যাতে k অপারেশনের পর অ্যারের যোগফল সর্বাধিক হয়।
যদি ইনপুট arr[] = {7, -3, 5, 4, -1} হয় তবে সর্বোচ্চ যোগফল হবে ২০।
- প্রথমে -3 কে 네가েট করুন। এখন অ্যারে হয় {7, 3, 5, 4, -1}
- পরে -1 কে 네가েট করুন। এখন অ্যারে হয় {7, 3, 5, 4, 1}
অ্যালগরিদম
1. বর্তমান অপারেশনের জন্য অ্যারেতে ন্যূনতম উপাদান arr[i]-কে -arr[i] দিয়ে রিপ্লেস করুন। 2. একবার ন্যূনতম উপাদান ০ হলে আর কোনো পরিবর্তন প্রয়োজন নেই। এইভাবে K অপারেশনের পর অ্যারের যোগফল সর্বাধিক করা যায়।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int* arr, int n, int k) {
for (int i = 1; i <= k; ++i) {
int minValue = INT_MAX;
int index = -1;
for (int j = 0; j < n; ++j) {
if (arr[j] < minValue) {
minValue = arr[j];
index = j;
}
}
if (minValue == 0) break;
arr[index] = -arr[index];
}
int sum = 0;
for (int i = 0; i < n; ++i) sum += arr[i];
return sum;
}
int main() {
int arr[] = {7, -3, 5, 4, -1};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << "Maximum sum = " << getMaxSum(arr, n, k) << endl;
return 0;
}
আউটপুট
Maximum sum = 20
