#practiceLinkDiv { näyttö: ei mitään !tärkeää; }Annettu joukko kokonaislukuja ja luku k. Voimme yhdistää kaksi taulukon numeroa, jos niiden välinen ero on ehdottomasti pienempi kuin k. Tehtävänä on löytää suurin mahdollinen hajaparien summa. P-parien summa on kaikkien 2P parien summa.
Esimerkkejä:
Suositeltu käytäntö Parit, joilla on tietty ero Kokeile sitä!Syöte : arr[] = {3 5 10 15 17 12 9} K = 4
Lähtö: 62
Selitys:
Sitten disjunktiparit, joiden ero on pienempi kuin K, ovat (3 5) (10 12) (15 17)
Joten maksimisumma, jonka voimme saada, on 3 + 5 + 12 + 10 + 15 + 17 = 62
Huomaa, että vaihtoehtoinen tapa muodostaa hajapareja on (3 5) (9 12) (15 17), mutta tämä parittaminen tuottaa pienemmän summan.
Syöte : arr[] = {5 15 10 300} k = 12
Lähtö: 25
Lähestyä: Ensin lajitellaan annettu taulukko kasvavaan järjestykseen. Kun taulukko on lajiteltu, kuljemme taulukon läpi. Jokaisen elementin kohdalla yritämme ensin yhdistää sen edellisen elementin kanssa. Miksi suosimme edellistä elementtiä? Olkoon arr[i] pariksi arr[i-1] ja arr[i-2] (eli 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.
Nyt huomioiden yllä olevat tosiasiat voimme muotoilla dynaamisen ohjelmointiratkaisumme kuten alla
Olkoon dp[i] suurin disjunktiparin summa, jonka voimme saavuttaa käyttämällä taulukon ensimmäisiä i-elementtejä. Oletetaan, että olemme tällä hetkellä sijalla i, niin meillä on kaksi mahdollisuutta.
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]
Yllä oleva iteraatio kestää O(N) aikaa ja taulukon lajittelu O(N log N) aikaa, joten ratkaisun kokonaisaikamonimutkaisuus on O(N log N)
Toteutus:
C++// C++ program to find maximum pair sum whose // difference is less than K #include
// 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 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# 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 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 ?> <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>
Lähtö
62
Aika monimutkaisuus: O(N Log N)
Aputila: O(N)
Alla on Amit Sanen tarjoama optimoitu ratkaisu
Toteutus:
C++// C++ program to find maximum pair sum whose // difference is less than K #include
// 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 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# 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 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 ?> <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((ab)=>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>
Lähtö
62
Aika monimutkaisuus: O(N Log N)
Aputila: O(1)