C ++中具有特定差异的对的最大和
在本教程中,我们将讨论一个程序,以查找具有特定差异的最大对。
为此,我们将提供一个包含整数和值K的数组。我们的任务是将差小于K的元素配对,并最终找到不相交集合中元素的最大和。
示例
#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