给定一个整数数组和一个数k。如果数组中的两个数之间的差严格小于k，我们可以对它们进行配对。任务是找到不相交对的最大可能和。P对之和是所有2P对数之和。
null
例如：
输入： arr[]={3,5,10,15,17,12,9}，K=4 输出： 62 说明： 那么差小于K的不相交对是，（3,5），（10,12），（15,17） 所以我们能得到的最大和是3+5+12+10+15+17=62 注意，形成不相交对的另一种方法是，（3，5），（9，12），（15，17），但这种配对产生的和较小。
输入： arr[]={5,15,10300}，k=12 输出： 25
方法： 首先，我们按递增顺序对给定数组进行排序。数组排序后，我们遍历数组。对于每个元素，我们首先尝试将其与前一个元素配对。为什么我们更喜欢前面的元素？设arr[i]可以与arr[i-1]和arr[i-2]配对（即arr[i]–arr[i-1]
Pair up i with (i-1)th element, i.e. dp[i] = dp[i-2] + arr[i] + arr[i-1] Don't pair up, i.e. dp[i] = dp[i-1]
上面的迭代需要O（N）个时间，数组的排序需要O（N logn）个时间，所以解决方案的总时间复杂度为O（N logn）
C++
// C++ program to find maximum pair sum whose // difference is less than K #include <bits/stdc++.h> using namespace std; // method to return maximum sum we can get by // finding less than K difference pair int maxSumPairWithDifferenceLessThanK( int arr[], int N, int K) { // Sort input array in ascending order. sort(arr, arr+N); // dp[i] denotes the maximum disjoint pair sum // we can achieve using first i elements int dp[N]; // if no element then dp value will be 0 dp[0] = 0; for ( int i = 1; i < N; i++) { // first give previous value to dp[i] i.e. // no pairing with (i-1)th element dp[i] = dp[i-1]; // if current and previous element can form a pair if (arr[i] - arr[i-1] < K) { // update dp[i] by choosing maximum between // pairing and not pairing 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]); } } // last index will have the result return dp[N - 1]; } // Driver code to test above methods 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; } |
JAVA
// Java program to find maximum pair sum whose // difference is less than K import java.io.*; import java.util.*; class GFG { // method to return maximum sum we can get by // finding less than K difference pair static int maxSumPairWithDifferenceLessThanK( int arr[], int N, int K) { // Sort input array in ascending order. Arrays.sort(arr); // dp[i] denotes the maximum disjoint pair sum // we can achieve using first i elements int dp[] = new int [N]; // if no element then dp value will be 0 dp[ 0 ] = 0 ; for ( int i = 1 ; i < N; i++) { // first give previous value to dp[i] i.e. // no pairing with (i-1)th element dp[i] = dp[i- 1 ]; // if current and previous element can form a pair if (arr[i] - arr[i- 1 ] < K) { // update dp[i] by choosing maximum between // pairing and not pairing if (i >= 2 ) dp[i] = Math.max(dp[i], dp[i- 2 ] + arr[i] + arr[i- 1 ]); else dp[i] = Math.max(dp[i], arr[i] + arr[i- 1 ]); } } // last index will have the result return dp[N - 1 ]; } // Driver code to test above methods public static void main (String[] args) { int arr[] = { 3 , 5 , 10 , 15 , 17 , 12 , 9 }; int N = arr.length; int K = 4 ; System.out.println ( maxSumPairWithDifferenceLessThanK( arr, N, K)); } } //This code is contributed by vt_m. |
Python3
# Python3 program to find maximum pair # sum whose difference is less than K # method to return maximum sum we can # get by get by finding less than K # difference pair def maxSumPairWithDifferenceLessThanK(arr, N, K): # Sort input array in ascending order. arr.sort() # dp[i] denotes the maximum disjoint # pair sum we can achieve using first # i elements dp = [ 0 ] * N # if no element then dp value will be 0 dp[ 0 ] = 0 for i in range ( 1 , N): # first give previous value to # dp[i] i.e. no pairing with # (i-1)th element dp[i] = dp[i - 1 ] # if current and previous element # can form a pair if (arr[i] - arr[i - 1 ] < K): # update dp[i] by choosing # maximum between pairing # and not pairing 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 ]); # last index will have the result return dp[N - 1 ] # Driver code to test above methods arr = [ 3 , 5 , 10 , 15 , 17 , 12 , 9 ] N = len (arr) K = 4 print (maxSumPairWithDifferenceLessThanK(arr, N, K)) # This code is contributed by Smitha Dinesh Semwal |
C#
// C# program to find maximum pair sum whose // difference is less than K using System; class GFG { // method to return maximum sum we can get by // finding less than K difference pair static int maxSumPairWithDifferenceLessThanK( int []arr, int N, int K) { // Sort input array in ascending order. Array.Sort(arr); // dp[i] denotes the maximum disjoint pair sum // we can achieve using first i elements int []dp = new int [N]; // if no element then dp value will be 0 dp[0] = 0; for ( int i = 1; i < N; i++) { // first give previous value to dp[i] i.e. // no pairing with (i-1)th element dp[i] = dp[i-1]; // if current and previous element can form // a pair if (arr[i] - arr[i-1] < K) { // update dp[i] by choosing maximum // between pairing and not pairing if (i >= 2) dp[i] = Math.Max(dp[i], dp[i-2] + arr[i] + arr[i-1]); else dp[i] = Math.Max(dp[i], arr[i] + arr[i-1]); } } // last index will have the result return dp[N - 1]; } // Driver code to test above methods public static void Main () { int []arr = {3, 5, 10, 15, 17, 12, 9}; int N = arr.Length; int K = 4; Console.WriteLine( maxSumPairWithDifferenceLessThanK(arr, N, K)); } } // This code is contributed by anuj_67. |
PHP
<?php // Php program to find maximum pair sum whose // difference is less than K // method to return maximum sum we can get by // finding less than K difference pair function maxSumPairWithDifferenceLessThanK( $arr , $N , $K ) { // Sort input array in ascending order. sort( $arr ) ; // dp[i] denotes the maximum disjoint pair sum // we can achieve using first i elements $dp = array () ; // if no element then dp value will be 0 $dp [0] = 0; for ( $i = 1; $i < $N ; $i ++) { // first give previous value to dp[i] i.e. // no pairing with (i-1)th element $dp [ $i ] = $dp [ $i -1]; // if current and previous element can form a pair if ( $arr [ $i ] - $arr [ $i -1] < $K ) { // update dp[i] by choosing maximum between // pairing and not pairing 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]); } } // last index will have the result return $dp [ $N - 1]; } // Driver code $arr = array (3, 5, 10, 15, 17, 12, 9); $N = sizeof( $arr ) ; $K = 4; echo maxSumPairWithDifferenceLessThanK( $arr , $N , $K ); // This code is contributed by Ryuga ?> |
Javascript
<script> // Javascript program to find maximum pair sum whose // difference is less than K // method to return maximum sum we can get by // finding less than K difference pair function maxSumPairWithDifferenceLessThanK(arr, N, K) { // Sort input array in ascending order. arr.sort(); // dp[i] denotes the maximum disjoint pair sum // we can achieve using first i elements let dp = []; // if no element then dp value will be 0 dp[0] = 0; for (let i = 1; i < N; i++) { // first give previous value to dp[i] i.e. // no pairing with (i-1)th element dp[i] = dp[i-1]; // if current and previous element can form a pair if (arr[i] - arr[i-1] < K) { // update dp[i] by choosing maximum between // pairing and not pairing if (i >= 2) dp[i] = Math.max(dp[i], dp[i-2] + arr[i] + arr[i-1]); else dp[i] = Math.max(dp[i], arr[i] + arr[i-1]); } } // last index will have the result return dp[N - 1]; } // Driver code to test above methods let arr = [3, 5, 10, 15, 17, 12, 9]; let N = arr.length; let K = 4; document.write( maxSumPairWithDifferenceLessThanK( arr, N, K)); // This code is contributed by avijitmondal1998. </script> |
输出
62
时间复杂性： O（N日志N） 辅助空间： O（N）
Amit Sane提供的优化解决方案如下：，
C++
// C++ program to find maximum pair sum whose // difference is less than K #include <bits/stdc++.h> using namespace std; // Method to return maximum sum we can get by // finding less than K difference pairs int maxSumPair( int arr[], int N, int k) { int maxSum = 0; // Sort elements to ensure every i and i-1 is closest // possible pair sort(arr, arr + N); // To get maximum possible sum, // iterate from largest to // smallest, giving larger // numbers priority over smaller // numbers. for ( int i = N - 1; i > 0; --i) { // Case I: Diff of arr[i] and arr[i-1] // is less then K,add to maxSum // Case II: Diff between arr[i] and arr[i-1] is not // less then K, move to next i since with // sorting we know, arr[i]-arr[i-1] < // rr[i]-arr[i-2] and so on. if (arr[i] - arr[i - 1] < k) { // Assuming only positive numbers. maxSum += arr[i]; maxSum += arr[i - 1]; // When a match is found skip this pair --i; } } return maxSum; } // Driver code int main() { int arr[] = { 3, 5, 10, 15, 17, 12, 9 }; int N = sizeof (arr) / sizeof ( int ); int K = 4; cout << maxSumPair(arr, N, K); return 0; } |
JAVA
// Java program to find maximum pair sum whose // difference is less than K import java.io.*; import java.util.*; class GFG { // Method to return maximum sum we can get by // finding less than K difference pairs static int maxSumPairWithDifferenceLessThanK( int arr[], int N, int k) { int maxSum = 0 ; // Sort elements to ensure every i and i-1 is // closest possible pair Arrays.sort(arr); // To get maximum possible sum, // iterate from largest // to smallest, giving larger // numbers priority over // smaller numbers. for ( int i = N - 1 ; i > 0 ; --i) { // Case I: Diff of arr[i] and arr[i-1] is less // then K, add to maxSum // Case II: Diff between arr[i] and arr[i-1] is // not less then K, move to next i // since with sorting we know, arr[i]-arr[i-1] < // arr[i]-arr[i-2] and so on. if (arr[i] - arr[i - 1 ] < k) { // Assuming only positive numbers. maxSum += arr[i]; maxSum += arr[i - 1 ]; // When a match is found skip this pair --i; } } return maxSum; } // Driver code public static void main(String[] args) { int arr[] = { 3 , 5 , 10 , 15 , 17 , 12 , 9 }; int N = arr.length; int K = 4 ; System.out.println( maxSumPairWithDifferenceLessThanK(arr, N, K)); } } // This code is contributed by vt_m. |
Python3
# Python3 program to find maximum pair sum # whose difference is less than K # Method to return maximum sum we can # get by finding less than K difference # pairs def maxSumPairWithDifferenceLessThanK(arr, N, k): maxSum = 0 # Sort elements to ensure every i and # i-1 is closest possible pair arr.sort() # To get maximum possible sum, iterate # from largest to smallest, giving larger # numbers priority over smaller numbers. i = N - 1 while (i > 0 ): # Case I: Diff of arr[i] and arr[i-1] # is less then K, add to maxSum # Case II: Diff between arr[i] and # arr[i-1] is not less then K, # move to next i since with sorting # we know, arr[i]-arr[i-1] < arr[i]-arr[i-2] # and so on. if (arr[i] - arr[i - 1 ] < k): # Assuming only positive numbers. maxSum + = arr[i] maxSum + = arr[i - 1 ] # When a match is found skip this pair i - = 1 i - = 1 return maxSum # Driver Code arr = [ 3 , 5 , 10 , 15 , 17 , 12 , 9 ] N = len (arr) K = 4 print (maxSumPairWithDifferenceLessThanK(arr, N, K)) # This code is contributed by mits |
C#
// C# program to find maximum pair sum whose // difference is less than K using System; class GFG { // Method to return maximum sum we can get by // finding less than K difference pairs static int maxSumPairWithDifferenceLessThanK( int []arr, int N, int k) { int maxSum = 0; // Sort elements to ensure // every i and i-1 is closest // possible pair Array.Sort(arr); // To get maximum possible sum, // iterate from largest // to smallest, giving larger // numbers priority over // smaller numbers. for ( int i = N-1; i > 0; --i) { /* Case I: Diff of arr[i] and arr[i-1] is less then K, add to maxSum Case II: Diff between arr[i] and arr[i-1] is not less then K, move to next i since with sorting we know, arr[i]-arr[i-1] < arr[i]-arr[i-2] and so on.*/ if (arr[i] - arr[i-1] < k) { // Assuming only positive numbers. maxSum += arr[i]; maxSum += arr[i - 1]; // When a match is found // skip this pair --i; } } return maxSum; } // Driver Code public static void Main () { int []arr = {3, 5, 10, 15, 17, 12, 9}; int N = arr.Length; int K = 4; Console.Write( maxSumPairWithDifferenceLessThanK(arr, N, K)); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find maximum pair sum // whose difference is less than K // Method to return maximum sum we can // get by finding less than K difference // pairs function maxSumPairWithDifferenceLessThanK( $arr , $N , $k ) { $maxSum = 0; // Sort elements to ensure every i and // i-1 is closest possible pair sort( $arr ); // To get maximum possible sum, iterate // from largest to smallest, giving larger // numbers priority over smaller numbers. for ( $i = $N - 1; $i > 0; -- $i ) { // Case I: Diff of arr[i] and arr[i-1] // is less then K, add to maxSum // Case II: Diff between arr[i] and // arr[i-1] is not less then K, // move to next i since with sorting // we know, arr[i]-arr[i-1] < arr[i]-arr[i-2] // and so on. if ( $arr [ $i ] - $arr [ $i - 1] < $k ) { // Assuming only positive numbers. $maxSum += $arr [ $i ]; $maxSum += $arr [ $i - 1]; // When a match is found skip this pair -- $i ; } } return $maxSum ; } // Driver Code $arr = array (3, 5, 10, 15, 17, 12, 9); $N = sizeof( $arr ); $K = 4; echo maxSumPairWithDifferenceLessThanK( $arr , $N , $K ); // This code is contributed // by Sach_Code ?> |
Javascript
<script> // Javascript program to find // maximum pair sum whose // difference is less than K // Method to return maximum sum we can get by // finding less than K difference pairs function maxSumPairWithDifferenceLessThanK(arr, N, k) { var maxSum = 0; // Sort elements to ensure every i and i-1 is // closest possible pair arr.sort((a,b)=>a-b); // To get maximum possible sum, // iterate from largest // to smallest, giving larger // numbers priority over // smaller numbers. for (i = N - 1; i > 0; --i) { // Case I: Diff of arr[i] and arr[i-1] is less // then K, add to maxSum // Case II: Diff between arr[i] and arr[i-1] is // not less then K, move to next i // since with sorting we know, arr[i]-arr[i-1] < // arr[i]-arr[i-2] and so on. if (arr[i] - arr[i - 1] < k) { // Assuming only positive numbers. maxSum += arr[i]; maxSum += arr[i - 1]; // When a match is found skip this pair --i; } } return maxSum; } // Driver code var arr = [ 3, 5, 10, 15, 17, 12, 9 ]; var N = arr.length; var K = 4; document.write(maxSumPairWithDifferenceLessThanK(arr, N, K)); // This code is contributed by 29AjayKumar </script> |
输出
62
时间复杂性： O（N日志N） 辅助空间： O（1）
本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
