Tổng lớn nhất của các cặp có hiệu nhỏ hơn K trong C++

Cho mảng số nguyên và K. Ghép các cặp có hiệu < K (sau khi sắp xếp), mỗi phần tử chỉ thuộc 1 cặp. Tìm tổng lớn nhất của các phần tử trong các cặp được chọn.

Thuật toán (DP)

• Sắp xếp mảng tăng dần.
• dp[i]: tổng lớn nhất xét đến chỉ số i.
• dp[i] = dp[i-1] (không ghép i).
• Nếu arr[i] - arr[i-1] < K: dp[i] = max(dp[i], dp[i-2] + arr[i] + arr[i-1]) (ghép cặp i-1, i).
• Kết quả: dp[N-1].

Ví dụ triển khai (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;
}

Đầu ra

62