特定の差があるペアの最大合計
GfG Practice で試してみる 
#practiceLinkDiv { 表示: なし !重要; }
出力
出力
#practiceLinkDiv { 表示: なし !重要; } 整数の配列と数値 k が与えられたとします。配列の 2 つの数値の差が厳密に k 未満であれば、それらの数値をペアにすることができます。タスクは、素のペアの可能な最大合計を見つけることです。 P ペアの合計は、ペアのすべての 2P 数の合計です。
例:
推奨される実践方法 特定の違いがあるペア 試してみてください!入力 : 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 10 300} k = 12
出力: 25
アプローチ： まず、指定された配列を昇順に並べ替えます。配列がソートされたら、配列を走査します。すべての要素について、最初にその要素を前の要素とペアにすることを試みます。なぜ前の要素を好むのでしょうか? arr[i] を arr[i-1] および arr[i-2] とペアにすることができます (つまり、arr[i] – arr[i-1] < K and arr[i]-arr[i-2] < K). Since the array is sorted value of arr[i-1] would be more than arr[i-2]. Also we need to pair with difference less than k it means if arr[i-2] can be paired then arr[i-1] can also be paired in a sorted array.
上記の事実を観察すると、動的プログラミングのソリューションを次のように定式化できます。
dp[i] が、配列の最初の i 要素を使用して達成できる最大の素ペアの合計を表すものとします。現在 i 番目の位置にいると仮定すると、2 つの可能性があります。
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 log N) 時間がかかるため、ソリューションの合計時間計算量は O(N log N) になります。
実装：
C++ // C++ program to find maximum pair sum whose // difference is less than K #include 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 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 Log N)
補助スペース：O(N)
Amit Sane が提供した最適化されたソリューションを以下に示します。
実装：
C++ // C++ program to find maximum pair sum whose // difference is less than K #include 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 than Kadd to maxSum // Case II: Diff between arr[i] and arr[i-1] is not // less than 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 // than K add to maxSum // Case II: Diff between arr[i] and arr[i-1] is // not less than 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 than K add to maxSum # Case II: Diff between arr[i] and # arr[i-1] is not less than 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 than K add to maxSum Case II: Diff between arr[i] and arr[i-1] is not less than 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 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 than K add to maxSum // Case II: Diff between arr[i] and // arr[i-1] is not less than 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 // than K add to maxSum // Case II: Diff between arr[i] and arr[i-1] is // not less than 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 Log N)
補助スペース: O(1)
