C++-এ সঠিকভাবে K পরিবর্তনের পর অ্যারে থেকে সর্বোচ্চ যোগফল পাওয়া

আমাদের একটি ধনাত্মক ও ঋণাত্মক পূর্ণসংখ্যার অ্যারে এবং একটি সংখ্যা K দেওয়া আছে। কাজ হল অ্যারের উপাদানগুলিতে ঠিক K সংখ্যক পরিবর্তন করার পর সর্বোচ্চ যোগফল খুঁজে বের করা। একক পরিবর্তন অপারেশন হল একটি উপাদানকে -1 দিয়ে গুণ করা।

অ্যালগরিদম

• প্রথমে সব ঋণাত্মক সংখ্যাকে ধনাত্মক করতে হবে। এর জন্য অ্যারেটি সর্ট করুন।
• যদি ঋণাত্মক সংখ্যার সংখ্যা N, K-এর চেয়ে কম হয় (N < K), তবে N অপারেশনের পর সব উপাদান ধনাত্মক হয়ে যাবে এবং অবশিষ্ট (K-N) অপারেশন থাকবে।
• যদি (K-N) জোড় সংখ্যা হয়, তবে অবশিষ্ট অপারেশনগুলো চিহ্ন পরিবর্তন করলেও যোগফলে কোনো প্রভাব পড়বে না।
• যদি (K-N) বিজোড় সংখ্যা হয়, তবে সর্বনিম্ন উপাদানটির চিহ্ন একবার পরিবর্তন করুন (এটি ঋণাত্মক হবে) কিন্তু সামগ্রিক যোগফল সর্বোচ্চ থাকবে।
• যদি N > K হয়, তবে K সংখ্যক ঋণাত্মক উপাদানের চিহ্ন পরিবর্তন করুন এবং অ্যারেটি যোগ করুন। যোগফল সর্বোচ্চ হবে।

উদাহরণ ১

Arr[] = { 0, -2, 6, 4, 8, 2, -3 }  K = 4

আউটপুট: Maximum array sum is : 25

ব্যাখ্যা: ৪টি পরিবর্তন হলো:

1. 0, 2, 6, 4, 8, 2, -3   (-2 → 2)
2. 0, 2, 6, 4, 8, 2, 3    (-3 → 3)
3. 0, -2, 6, 4, 8, 2, 3   (2 → -2)
4. 0, 2, 6, 4, 8, 2, 3    (-2 → 2)
সর্বোচ্চ যোগফল = 25

উদাহরণ ২

Arr[] = { -1, -2, -3, -4, -5, -6, -7 }  K = 4

আউটপুট: Maximum array sum is : 16

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

int returnSum(int arr[], int n, int k) {
    sort(arr, arr + n);               // অ্যারেটি সর্ট করুন
    for (int i = 0; i < n; i++) {
        if (k > 0 && arr[i] < 0) {    // ঋণাত্মক উপাদানগুলোকে ধনাত্মক করুন
            arr[i] = arr[i] * -1;
            k--;
        }
    }
    // যদি k বিজোড় থাকে, সর্বনিম্ন উপাদানটির চিহ্ন পরিবর্তন করুন
    if (k % 2 == 1) {
        int minVal = arr[0], pos = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] < minVal) {
                minVal = arr[i];
                pos = i;
            }
        }
        arr[pos] *= -1;
    }
    int sum = 0;
    for (int i = 0; i < n; i++) sum += arr[i];
    return sum;
}

int main() {
    int Arr[] = { -3, 4, -3, 6, 8 };
    int size = 5, K = 4;
    cout << "Maximum array sum after exactly k changes: " << returnSum(Arr, size, K) << endl;
    return 0;
}

আউটপুট: Maximum array sum that can be obtained after exactly k changes : 24