Dadas dos arrays de enteros positivos y distintos. La tarea es encontrar un par de las dos arrays con suma máxima.
Nota : el par debe contener un elemento de ambas arrays.
Ejemplos :
Input : arr1[] = {1, 2, 3}, arr2[] = {4, 5, 6}
Output : Max Sum = 9
Pair (3, 6) has the maximum sum.
Input : arr1[] = {10, 2, 3}, arr2[] = {3, 4, 7}
Output : Max Sum = 17
Enfoque ingenuo : un enfoque simple es ejecutar dos bucles anidados para generar todos los pares posibles y encontrar el par con la suma máxima.
Complejidad de tiempo: O(N*M), donde N es la longitud de la primera array y M es la longitud de la segunda array.
Enfoque eficiente : un enfoque eficiente es observar que los elementos que son máximos en las arrays respectivas contribuirán al par de suma máxima. Entonces, la tarea se reduce a encontrar el máximo de elementos de ambas arrays e imprimir su suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find maximum sum
// pair from two arrays
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum sum
// pair from two arrays
int maxSumPair(int arr1[], int n1, int arr2[], int n2)
{
int max1 = INT_MIN; // max from 1st array
int max2 = INT_MIN; // max from 2nd array
// Find max from 1st array
for (int i = 0; i < n1; i++) {
if (arr1[i] > max1)
max1 = arr1[i];
}
// Find max from 2nd array
for (int i = 0; i < n2; i++) {
if (arr2[i] > max2)
max2 = arr2[i];
}
// Return sum of max from both arrays
return max1 + max2;
}
// Driver Code
int main()
{
int arr1[] = { 10, 2, 3 };
int arr2[] = { 3, 4, 7 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout << maxSumPair(arr1, n1, arr2, n2);
return 0;
}
Java
//Java program to find maximum sum
//pair from two arrays
public class AAB {
//Function to find maximum sum
//pair from two arrays
static int maxSumPair(int arr1[], int n1, int arr2[], int n2)
{
int max1 = Integer.MIN_VALUE; // max from 1st array
int max2 = Integer.MIN_VALUE; // max from 2nd array
// Find max from 1st array
for (int i = 0; i < n1; i++) {
if (arr1[i] > max1)
max1 = arr1[i];
}
// Find max from 2nd array
for (int i = 0; i < n2; i++) {
if (arr2[i] > max2)
max2 = arr2[i];
}
// Return sum of max from both arrays
return max1 + max2;
}
//Driver Code
public static void main(String[] args) {
int arr1[] = { 10, 2, 3 };
int arr2[] = { 3, 4, 7 };
int n1 = arr1.length;
int n2 = arr2.length;
System.out.println(maxSumPair(arr1, n1, arr2, n2));
}
}
Python3
# Python3 program to find maximum # sum pair from two arrays import sys # Function to find maximum sum # pair from two arrays def maxSumPair(arr1, n1, arr2, n2): max1 = -sys.maxsize -1 # max from 1st array max2 = -sys.maxsize -1 # max from 2nd array # Find max from 1st array for i in range(0, n1): if (arr1[i] > max1): max1 = arr1[i] # Find max from 2nd array for i in range(0, n2): if (arr2[i] > max2): max2 = arr2[i] # Return sum of max from # both arrays return max1 + max2 # Driver Code arr1 = [ 10, 2, 3 ] arr2 = [ 3, 4, 7 ] n1 = len(arr1) n2 = len(arr2) print(maxSumPair(arr1, n1, arr2, n2)) # This code is contributed # by Yatin Gupta
C#
// C# program to find maximum sum
//pair from two arrays
using System;
public class AAB {
//Function to find maximum sum
//pair from two arrays
static int maxSumPair(int []arr1, int n1, int []arr2, int n2)
{
int max1 = int.MinValue; // max from 1st array
int max2 = int.MinValue; // max from 2nd array
// Find max from 1st array
for (int i = 0; i < n1; i++) {
if (arr1[i] > max1)
max1 = arr1[i];
}
// Find max from 2nd array
for (int i = 0; i < n2; i++) {
if (arr2[i] > max2)
max2 = arr2[i];
}
// Return sum of max from both arrays
return max1 + max2;
}
//Driver Code
public static void Main() {
int []arr1 = { 10, 2, 3 };
int []arr2 = { 3, 4, 7 };
int n1 = arr1.Length;
int n2 = arr2.Length;
Console.Write(maxSumPair(arr1, n1, arr2, n2));
}
}
/*This code is contributed by 29AjayKumar*/
PHP
<?php
// PHP program to find maximum sum
// pair from two arrays
// Function to find maximum sum
// pair from two arrays
function maxSumPair($arr1, $n1, $arr2, $n2)
{
$max1 = -1; // max from 1st array
$max2 = -1; // max from 2nd array
// Find max from 1st array
for ($i = 0; $i < $n1; $i++)
{
if ($arr1[$i] > $max1)
$max1 = $arr1[$i];
}
// Find max from 2nd array
for ($i = 0; $i < $n2; $i++)
{
if ($arr2[$i] > $max2)
$max2 = $arr2[$i];
}
// Return sum of max from both arrays
return $max1 + $max2;
}
// Driver Code
$arr1 = array( 10, 2, 3 );
$arr2 = array( 3, 4, 7 );
$n1 = count($arr1);
$n2 = count($arr2);
echo maxSumPair($arr1, $n1, $arr2, $n2);
// This code is contributed by Rajput-Ji
?>
Javascript
<script>
// Javascript program to find maximum sum
// pair from two arrays
// Function to find maximum sum
// pair from two arrays
function maxSumPair(arr1,n1,arr2,n2)
{
// max from 1st array
let max1 = Number.MIN_VALUE;
// max from 2nd array
let max2 = Number.MIN_VALUE;
// Find max from 1st array
for (let i = 0; i < n1; i++) {
if (arr1[i] > max1)
max1 = arr1[i];
}
// Find max from 2nd array
for (let i = 0; i < n2; i++) {
if (arr2[i] > max2)
max2 = arr2[i];
}
// Return sum of max from both arrays
return max1 + max2;
}
// Driver Code
let arr1=[10, 2, 3 ];
let arr2=[3, 4, 7 ];
let n1 = arr1.length;
let n2 = arr2.length;
document.write(maxSumPair(arr1, n1, arr2, n2));
// This code is contributed by rag2127
</script>
Producción:
17
Complejidad de tiempo : O (N + M), donde N es la longitud de la primera array y M es la longitud de la segunda array.