सरणी और मान K दिया गया है। ऐसे जोड़े बनाएं जिनका अंतर K से कम हो, और असंयुक्त जोड़ों के तत्वों का अधिकतम योग खोजें।
उदाहरण: {3, 5, 10, 15, 17, 12, 9}, K=4 → अधिकतम योग 62।
समाधान दृष्टिकोण (DP)
- सरणी को सॉर्ट करें।
dp[i]= पहले i+1 तत्वों से अधिकतम योग।dp[0] = 0।- i = 1 से N-1 तक:
dp[i] = dp[i-1](i-वां तत्व न लें)।- यदि
arr[i] - arr[i-1] < K:- यदि i >= 2:
dp[i] = max(dp[i], dp[i-2] + arr[i] + arr[i-1])। - अन्यथा:
dp[i] = max(dp[i], arr[i] + arr[i-1])।
- यदि i >= 2:
dp[N-1]वापस करें।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
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