Dada una array de enteros y un número k. Podemos emparejar dos números del arreglo si la diferencia entre ellos es estrictamente menor que k. La tarea es encontrar la suma máxima posible de pares disjuntos. La suma de P pares es la suma de todos los 2P números de pares.
Ejemplos:
Entrada: arr[] = {3, 5, 10, 15, 17, 12, 9}, K = 4
Salida: 62
Explicación:
Entonces los pares disjuntos con diferencia menor que K son, (3, 5), (10, 12 ), (15, 17)
Entonces, la suma máxima que podemos obtener es 3 + 5 + 12 + 10 + 15 + 17 = 62
Tenga en cuenta que una forma alternativa de formar pares disjuntos es (3, 5), (9, 12) , (15, 17), pero este emparejamiento produce una suma menor.Entrada: arr[] = {5, 15, 10, 300}, k = 12
Salida: 25
Enfoque: Primero, ordenamos la array dada en orden creciente. Una vez que se ordena la array, recorremos la array. Para cada elemento, intentamos emparejarlo primero con su elemento anterior. ¿Por qué preferimos el elemento anterior? Supongamos que arr[i] puede emparejarse con arr[i-1] y arr[i-2] (es decir, arr[i] – arr[i-1] < K y arr[i]-arr[i-2] < K). Dado que la array está ordenada, el valor de arr[i-1] sería mayor que arr[i-2]. Además, necesitamos emparejar con una diferencia menor que k, lo que significa que si arr[i-2] se puede emparejar, entonces arr[i-1] también se puede emparejar en una array ordenada.
Ahora, observando los hechos anteriores, podemos formular nuestra solución de programación dinámica de la siguiente manera,
Sea dp[i] la máxima suma de pares disjuntos que podemos lograr usando los primeros i elementos de la array. Supongamos que actualmente estamos en la i-ésima posición, entonces hay dos posibilidades para nosotros.
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]
La iteración anterior toma tiempo O (N) y la clasificación de la array tomará tiempo O (N log N), por lo que la complejidad de tiempo total de la solución será O (N log N)
Implementación:
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>
Producción
62
Complejidad temporal: O(N Log N)
Espacio auxiliar: O(N)
A continuación se proporciona una solución optimizada aportada por Amit Sane,
Implementación:
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 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] <
// 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
// 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>
Producción
62
Complejidad temporal: O(N Log N)
Espacio auxiliar: O(1)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA