সমস্যা বিবরণ
একটি অ্যারে arr[] এবং সংখ্যা M দেওয়া আছে। অ্যারেতে থেকে Mটি উপাদান বাছাই করতে হবে যাতে বাছাই করা উপাদানগুলোর যোগফল এবং বাকি উপাদানগুলোর যোগফলের পার্থক্য পরম মান সর্বোচ্চ হয়।
উদাহরণ: arr = {3,1,6,9,4}, M = 3 → আউটপুট 15। বড় ৩টি: 4,6,9 (যোগফল ১৯), বাকি: 3,1 (যোগফল ৪) → পার্থক্য |19-4| = 15।
সমাধানের পদ্ধতি
গবেষণা: সর্বোচ্চ পার্থক্য পাওয়া যায় либо Mটি সবচেয়ে বড় উপাদান নিলে, অথবা Mটি সবচেয়ে ছোট উপাদান নিলে।
- অ্যারেটি সর্ট করুন।
sumMin= প্রথমMটি উপাদানের যোগফল (ছোটগুলো)।sumMax= শেষMটি উপাদানের যোগফল (বড়গুলো)।totalSum= সব উপাদানের যোগফল।- উত্তর =
max(|sumMax - (totalSum - sumMax)|, |sumMin - (totalSum - sumMin)|)।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int maxWeightDifference(int arr[], int N, int M) {
int maxAbsDiff = -1000;
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];
}
maxAbsDiff = max(abs(sumMax - (arrSum - sumMax)), abs(sumMin - (arrSum - sumMin)));
return maxAbsDiff;
}
int main() {
int arr[] = {3, 1, 6, 9, 4};
int M = 3;
int N = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum weight difference is " << maxWeightDifference(arr, N, M);
return 0;
}
আউটপুট
The maximum weight difference is 15
