এই টিউটোরিয়ালে, আমরা নির্দিষ্ট পার্থক্য সহ সর্বাধিক জোড়ার যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।
এর জন্য আমাদেরকে পূর্ণসংখ্যা এবং একটি মান K সমন্বিত একটি অ্যারে সরবরাহ করা হবে। আমাদের কাজ হল K-এর চেয়ে কম পার্থক্য থাকা উপাদানগুলিকে জোড়া দেওয়া এবং অবশেষে বিচ্ছিন্ন সেটগুলিতে উপাদানগুলির সর্বাধিক যোগফল খুঁজে বের করা৷
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
//returning maximum sum of disjoint pairs
int maxSumPairWithDifferenceLessThanK(int arr[], int N, int K){
sort(arr, arr+N);
int dp[N];
dp[0] = 0;
for (int i = 1; i < N; i++) {
dp[i] = dp[i-1];
if (arr[i] - arr[i-1] < K) {
if (i >= 2)
dp[i] = max(dp[i], dp[i-2] + arr[i] + arr[i-1]);
else
dp[i] = max(dp[i], arr[i] + arr[i-1]);
}
}
return dp[N - 1];
}
int main() {
int arr[] = {3, 5, 10, 15, 17, 12, 9};
int N = sizeof(arr)/sizeof(int);
int K = 4;
cout << maxSumPairWithDifferenceLessThanK(arr, N, K);
return 0;
} আউটপুট
62
