Maximale Summe von Paaren mit spezifischer Differenz
Probieren Sie es bei GfG Practice aus 
#practiceLinkDiv { display: none !important; }
Ausgabe
Ausgabe
#practiceLinkDiv { display: none !important; } Gegeben sei ein Array von ganzen Zahlen und eine Zahl k. Wir können zwei Zahlen des Arrays paaren, wenn die Differenz zwischen ihnen unbedingt kleiner als k ist. Die Aufgabe besteht darin, die maximal mögliche Summe disjunkter Paare zu finden. Die Summe von P Paaren ist die Summe aller 2P Anzahlen von Paaren.
Beispiele:
Empfohlene Praxis Paare mit spezifischem Unterschied Probieren Sie es aus!Eingabe: arr[] = {3 5 10 15 17 12 9} K = 4
Ausgabe : 62
Erläuterung:
Dann sind disjunkte Paare mit einer Differenz kleiner als K (3 5) (10 12) (15 17)
Die maximale Summe, die wir erhalten können, ist also 3 + 5 + 12 + 10 + 15 + 17 = 62
Beachten Sie, dass eine alternative Möglichkeit zur Bildung disjunkter Paare (3 5) (9 12) (15 17) ist, diese Paarung jedoch eine geringere Summe ergibt.Eingabe: arr[] = {5 15 10 300} k = 12
Ausgabe : 25
Ansatz: Zuerst sortieren wir das angegebene Array in aufsteigender Reihenfolge. Sobald das Array sortiert ist, durchlaufen wir das Array. Für jedes Element versuchen wir, es zuerst mit seinem vorherigen Element zu koppeln. Warum bevorzugen wir das vorherige Element? Lassen Sie arr[i] mit arr[i-1] und arr[i-2] gepaart werden (d. h. 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.
Unter Berücksichtigung der oben genannten Fakten können wir nun unsere dynamische Programmierlösung wie folgt formulieren
Sei dp[i] die maximale disjunkte Paarsumme, die wir mit den ersten i Elementen des Arrays erreichen können. Angenommen, wir befinden uns derzeit an der i-ten Position, dann gibt es für uns zwei Möglichkeiten.
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]
Die obige Iteration benötigt O(N) Zeit und das Sortieren des Arrays benötigt O(N log N) Zeit, sodass die Gesamtzeitkomplexität der Lösung O(N log N) beträgt.
Durchführung:
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>
Ausgabe
62
Zeitkomplexität: O(N Log N)
Hilfsraum: O(N)
Eine optimierte Lösung von Amit Sane ist unten aufgeführt
Durchführung:
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>
Ausgabe
62
Zeitkomplexität: O(N Log N)
Hilfsraum: O(1)
![Top 10 der größten Städte in den Vereinigten Staaten nach Einwohnerzahl [Aktualisierte Liste 2024]](https://techcodeview.com/img/us-gk/09/top-10-largest-cities-united-states-population-ranked.webp)
