Tổng tối đa của các cặp với sự khác biệt cụ thể trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm tổng số tối đa của các cặp với sự khác biệt cụ thể.

Đối với điều này, chúng ta sẽ được cung cấp một mảng chứa các số nguyên và giá trị K. Nhiệm vụ của chúng ta là ghép nối các phần tử có hiệu số nhỏ hơn K và cuối cùng tìm tổng lớn nhất của các phần tử trong các tập hợp rời rạc.

Ví dụ

#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;
}

Đầu ra

62