একটি অ্যারে arr[] ও সংখ্যা M দেওয়া আছে। অ্যারেটি থেকে M সংখ্যক উপাদান বাছাই করতে হবে যাতে বাছাইকৃত উপাদানগুলোর যোগফল ও বাকি উপাদানগুলোর যোগফলের পরম পার্থক্য সর্বোচ্চ হয়।
উদাহরণ
arr[] = {3, 1, 6, 9, 4}, M = 3
আউটপুট: 15
ব্যাখ্যা: {4,6,9} বাছাই করলে যোগফল ১৯। বাকি {3,1} যোগফল ৪। পার্থক্য |19-4| = 15।
অ্যালগরিদম
- সর্বোচ্চ পার্থক্য হয়ে থাকে
Mটি সর্বোচ্চ বাMটি সর্বনিম্ন উপাদান বাছাই করলে। - অ্যারেটি সর্ট করুন।
Mটি ছোট ওMটি বড় উপাদানের যোগফল বের করুন।- উভয় কেসের পার্থক্য থেকে সর্বোচ্চটা নিন।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int maxWeightDifference(int arr[], int N, int M) {
sort(arr, arr + N);
int sumMin = 0, sumMax = 0, arrSum = 0;
for (int i = 0; i < N; i++) {
arrSum += arr[i];
if (i < M) sumMin += arr[i];
if (i >= N-M) sumMax += arr[i];
}
int diff1 = abs(sumMax - (arrSum - sumMax));
int diff2 = abs(sumMin - (arrSum - sumMin));
return max(diff1, diff2);
}
int main() {
int arr[] = {3, 1, 6, 9, 4};
int M = 3, N = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum weight difference is " << maxWeightDifference(arr, N, M);
return 0;
}
আউটপুট: The maximum weight difference is 15
