ผลรวมสูงสุดของคู่ที่มีความแตกต่างเฉพาะใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมเพื่อค้นหาผลรวมสูงสุดของคู่ที่มีความแตกต่างเฉพาะ

สำหรับสิ่งนี้ เราจะได้รับอาร์เรย์ที่มีจำนวนเต็มและค่า 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