資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究具有特定差值的數對的最大和 C++ 程式
在這個問題中，我們給定一個包含 n 個整數的陣列 arr[] 和一個數字 d。我們的任務是建立一個程式，用 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。否則，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
更新於: 2020-12-09
161 次檢視
廣告