Dada una array arr de tamaño N y un número entero K . La tarea es encontrar el par de enteros tales que su suma sea máxima y menor que K
Ejemplos:
Entrada: arr = {30, 20, 50}, K = 70
Salida: 30, 20
30 + 20 = 50, que es la suma máxima posible que es menor que K
Entrada: arr = {5, 20, 110, 100, 10}, K = 85
Salida: 20, 10
Enfoque:
Un enfoque eficiente es ordenar la array dada y encontrar el elemento que es mayor o igual que K. Si se encuentra en el índice p , tenemos que encontrar pares solo entre arr[0, …, p-1] . Ejecute bucles anidados. Uno para cuidar del primer elemento del par y el otro para cuidar del segundo elemento del par. Mantenga una variable maxsum y otras dos variables a y b para realizar un seguimiento de la posible solución. Inicialice maxsum a 0 . Encuentre A[i] + A[j] (suponiendo que i se ejecuta en el bucle externo y j en el bucle interno). Si es mayor que maxsumluego actualice maxsum con esta suma y cambie a y b por los elementos i’th y j’th de esta array.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find pair with largest
// sum which is less than K in the array
#include <bits/stdc++.h>
using namespace std;
// Function to find pair with largest
// sum which is less than K in the array
void Max_Sum(int arr[], int n, int k)
{
// To store the break point
int p = n;
// Sort the given array
sort(arr, arr + n);
// Find the break point
for (int i = 0; i < n; i++)
{
// No need to look beyond i'th index
if (arr[i] >= k) {
p = i;
break;
}
}
int maxsum = 0, a, b;
// Find the required pair
for (int i = 0; i < p; i++)
{
for (int j = i + 1; j < p; j++)
{
if (arr[i] + arr[j] < k and arr[i] + arr[j] >
maxsum)
{
maxsum = arr[i] + arr[j];
a = arr[i];
b = arr[j];
}
}
}
// Print the required answer
cout << a << " " << b;
}
// Driver code
int main()
{
int arr[] = {5, 20, 110, 100, 10}, k = 85;
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
Max_Sum(arr, n, k);
return 0;
}
Java
// Java program to find pair with largest
// sum which is less than K in the array
import java.util.Arrays;
class GFG
{
// Function to find pair with largest
// sum which is less than K in the array
static void Max_Sum(int arr[], int n, int k)
{
// To store the break point
int p = n;
// Sort the given array
Arrays.sort(arr);
// Find the break point
for (int i = 0; i < n; i++)
{
// No need to look beyond i'th index
if (arr[i] >= k)
{
p = i;
break;
}
}
int maxsum = 0, a = 0, b = 0;
// Find the required pair
for (int i = 0; i < p; i++)
{
for (int j = i + 1; j < p; j++)
{
if (arr[i] + arr[j] < k &&
arr[i] + arr[j] > maxsum)
{
maxsum = arr[i] + arr[j];
a = arr[i];
b = arr[j];
}
}
}
// Print the required answer
System.out.print( a + " " + b);
}
// Driver code
public static void main (String[] args)
{
int []arr = {5, 20, 110, 100, 10};
int k = 85;
int n = arr.length;
// Function call
Max_Sum(arr, n, k);
}
}
// This code is contributed by anuj_67..
Python3
# Python3 program to find pair with largest # sum which is less than K in the array # Function to find pair with largest # sum which is less than K in the array def Max_Sum(arr, n, k): # To store the break point p = n # Sort the given array arr.sort() # Find the break point for i in range(0, n): # No need to look beyond i'th index if (arr[i] >= k): p = i break maxsum = 0 a = 0 b = 0 # Find the required pair for i in range(0, p): for j in range(i + 1, p): if(arr[i] + arr[j] < k and arr[i] + arr[j] > maxsum): maxsum = arr[i] + arr[j] a = arr[i] b = arr[j] # Print the required answer print(a, b) # Driver code arr = [5, 20, 110, 100, 10] k = 85 n = len(arr) # Function call Max_Sum(arr, n, k) # This code is contributed by Sanjit_Prasad
C#
// C# program to find pair with largest
// sum which is less than K in the array
using System;
class GFG
{
// Function to find pair with largest
// sum which is less than K in the array
static void Max_Sum(int []arr, int n, int k)
{
// To store the break point
int p = n;
// Sort the given array
Array.Sort(arr);
// Find the break point
for (int i = 0; i < n; i++)
{
// No need to look beyond i'th index
if (arr[i] >= k)
{
p = i;
break;
}
}
int maxsum = 0, a = 0, b = 0;
// Find the required pair
for (int i = 0; i < p; i++)
{
for (int j = i + 1; j < p; j++)
{
if (arr[i] + arr[j] < k &&
arr[i] + arr[j] > maxsum)
{
maxsum = arr[i] + arr[j];
a = arr[i];
b = arr[j];
}
}
}
// Print the required answer
Console.WriteLine( a + " " + b);
}
// Driver code
public static void Main ()
{
int []arr = {5, 20, 110, 100, 10};
int k = 85;
int n = arr.Length;
// Function call
Max_Sum(arr, n, k);
}
}
// This code is contributed by anuj_67..
Javascript
<script>
// Javascript program to find pair with largest
// sum which is less than K in the array
// Function to find pair with largest
// sum which is less than K in the array
function Max_Sum(arr, n, k)
{
// To store the break point
let p = n;
// Sort the given array
arr.sort(function(a, b){return a - b});
// Find the break point
for (let i = 0; i < n; i++)
{
// No need to look beyond i'th index
if (arr[i] >= k)
{
p = i;
break;
}
}
let maxsum = 0, a = 0, b = 0;
// Find the required pair
for (let i = 0; i < p; i++)
{
for (let j = i + 1; j < p; j++)
{
if (arr[i] + arr[j] < k &&
arr[i] + arr[j] > maxsum)
{
maxsum = arr[i] + arr[j];
a = arr[i];
b = arr[j];
}
}
}
// Print the required answer
document.write( a + " " + b + "</br>");
}
let arr = [5, 20, 110, 100, 10];
let k = 85;
let n = arr.length;
// Function call
Max_Sum(arr, n, k);
</script>
Producción
10 20
Complejidad del tiempo: O(N^2)
Enfoque eficiente: método de dos punteros
Después de ordenar, podemos colocar dos punteros en los extremos izquierdo y derecho de la array. El par deseado se puede encontrar siguiendo los siguientes pasos:
- Encuentre la suma actual de los valores en ambos punteros.
- Si la suma es menor que k:
- actualice la respuesta con el máximo de la respuesta anterior y la suma actual.
- aumentar el puntero izquierdo.
- Else Disminuye el puntero derecho.
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find max sum less than k
int maxSum(vector<int> arr, int k)
{
// Sort the array
sort(arr.begin(), arr.end());
int n = arr.size(), l = 0, r = n - 1, ans = 0;
// While l is less than r
while (l < r) {
if (arr[l] + arr[r] < k) {
ans = max(ans, arr[l] + arr[r]);
l++;
}
else {
r--;
}
}
return ans;
}
// Driver Code
int main()
{
vector<int> A = { 20, 10, 30, 100, 110 };
int k = 85;
// Function Call
cout << maxSum(A, k) << endl;
}
Python3
# Python program for above approach # Function to find max sum less than k def maxSum(arr, k): # Sort the array arr.sort() n,l = len(arr),0 r,ans = n - 1,0 # While l is less than r while (l < r): if (arr[l] + arr[r] < k): ans = max(ans, arr[l] + arr[r]) l += 1 else: r -= 1 return ans # Driver Code A = [20, 10, 30, 100, 110] k = 85 # Function Call print(maxSum(A, k)) # This code is contributed by shinjanpatra
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find max sum less than k
static int maxSum(int[] arr, int k)
{
// Sort the array
Array.Sort(arr);
int n = arr.Length, l = 0, r = n - 1, ans = 0;
// While l is less than r
while (l < r) {
if (arr[l] + arr[r] < k) {
ans = Math.Max(ans, arr[l] + arr[r]);
l++;
}
else {
r--;
}
}
return ans;
}
// Driver code
public static void Main ()
{
int[] A = { 20, 10, 30, 100, 110 };
int k = 85;
// Function Call
Console.WriteLine(maxSum(A, k));
}
}
// This code is contributed by target_2.
Javascript
<script>
// Javascript program for the above approach
// Function to find max sum less than k
function maxSum(arr, k)
{
// Sort the array
arr.sort((a,b)=>a-b);
var n = arr.length, l = 0, r = n - 1, ans = 0;
// While l is less than r
while (l < r) {
if (arr[l] + arr[r] < k) {
ans = Math.max(ans, arr[l] + arr[r]);
l++;
}
else {
r--;
}
}
return ans;
}
// Driver Code
var A = [20, 10, 30, 100, 110];
var k = 85;
// Function Call
document.write( maxSum(A, k));
</script>
Producción
50
Complejidad de tiempo : O(NlogN)
Complejidad del espacio : O(1)
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA