이 문제에서 n개의 정수와 숫자 d의 배열 arr[]이 제공됩니다. 우리의 임무는 C++에서 특정 차이를 갖는 쌍의 최대 합을 찾는 프로그램을 만드는 것입니다. .
문제 설명 − 쌍의 요소 차이가 d보다 작은 방식으로 쌍을 찾습니다. 이러한 모든 쌍의 합은 최대값이어야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
arr[] = {5, 9, 11, 7, 2, 12, 3} d = 5 출력
47
설명
Pairs that contribute to maximum sum: (3, 5), (7, 9), (11, 12). Sum = 3 + 5 + 7 + 9 + 11 + 12 = 47
솔루션 접근 방식
문제에 대한 간단하고 분명한 해결책은 모든 유효한 배열 쌍을 만든 다음 합계를 찾고 모든 합계의 최대값을 반환하는 것입니다. 그러나 이 솔루션은 효율적이지 않습니다.
문제에 대한 효율적인 솔루션은 동적 프로그래밍 접근 방식을 사용하는 것입니다. 여기에서 최대합을 구성하는 최적의 쌍을 찾을 것입니다. 이를 위해 우리는 정렬된 배열을 사용할 것이므로 먼저 주어진 배열을 정렬한 다음 작업합니다. 합을 찾기 위해 배열을 사용하여 현재 요소까지 쌍의 최대 합을 저장합니다. 이를 위해 현재 요소와 이전 요소가 쌍을 이루는지 확인합니다. 그렇다면 배열까지 maxSum에 쌍 합계를 추가합니다. 그렇지 않으면 최대값이 그대로 유지됩니다.
알고리즘
Initialize: DP[n]
1단계 -
For array arr[].
2단계
DP[0] = 0;
3단계 -
loop for i −> 1 to n
3.1단계 -
check if pairs with the previous element is possible. if(arr[i] − arr[i−1] < d).
3.2단계 -
if Yes, check if the current pair sum results in a greater value than the last considered sum and add the maximum value to the current sum. i.e. if( (DP[i−2] + arr[i−1] + arr[i]) > (DP[i−1])) −> DP[i] = (DP[i−2] + arr[i−1] + arr[i]), else −> DP[i] = DP[i−1].
3.3단계 -
an exception is for value i = 1, where no value of DP[i−2] is possible, in this case, DP[i−2] is not considered as it is the first pair sum.
4단계 -
Return DP[n−1].
예시
우리 솔루션의 작동을 설명하는 프로그램
#include <bits/stdc++.h>
using namespace std;
int CalcmaxPairSum(int arr[], int n, int d) {
sort(arr, arr+n);
int maxSumDP[n];
maxSumDP[0] = 0;
for (int i = 1; i < n; i++) {
maxSumDP[i] = maxSumDP[i−1];
if (arr[i] − arr[i−1] < d) {
if (i >= 2)
if(maxSumDP[i] < (maxSumDP[i−2] + arr[i−1] +
arr[i]))
maxSumDP[i] = (maxSumDP[i−2] + arr[i−1] +
arr[i]);
else
if(maxSumDP[i] < (arr[i−1] + arr[i]))
maxSumDP[i] = arr[i−1] + arr[i];
}
}
return maxSumDP[n−1];
}
int main() {
int arr[] = {5, 9, 11, 7, 2, 12, 3};
int n = 7, d = 5;
cout<<"The maximum sum of pairs with specific difference is "<<CalcmaxPairSum(arr, n, d);
return 0;
} 출력
The maximum sum of pairs with specific difference is 47