Dada una array con enteros +ive y -ive, devuelve un par con el producto más alto.
Ejemplos:
Input: arr[] = {1, 4, 3, 6, 7, 0}
Output: {6,7}
Input: arr[] = {-1, -3, -4, 2, 0, -5}
Output: {-4,-5}
Una solución simple es considerar cada par y realizar un seguimiento del producto máximo. A continuación se muestra la implementación de esta solución simple.
C++
// A simple C++ program to find max product pair in
// an array of integers
#include<bits/stdc++.h>
using namespace std;
// Function to find maximum product pair in arr[0..n-1]
void maxProduct(int arr[], int n)
{
if (n < 2)
{
cout << "No pairs exists\n";
return;
}
// Initialize max product pair
int a = arr[0], b = arr[1];
// Traverse through every possible pair
// and keep track of max product
for (int i=0; i<n; i++)
for (int j=i+1; j<n; j++)
if (arr[i]*arr[j] > a*b)
a = arr[i], b = arr[j];
cout << "Max product pair is {" << a << ", "
<< b << "}";
}
// Driver program to test
int main()
{
int arr[] = {1, 4, 3, 6, 7, 0};
int n = sizeof(arr)/sizeof(arr[0]);
maxProduct(arr, n);
return 0;
}
Java
// JAVA Code to Find a pair with maximum
// product in array of Integers
import java.util.*;
class GFG {
// Function to find maximum product pair
// in arr[0..n-1]
static void maxProduct(int arr[], int n)
{
if (n < 2)
{
System.out.println("No pairs exists");
return;
}
// Initialize max product pair
int a = arr[0], b = arr[1];
// Traverse through every possible pair
// and keep track of max product
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] * arr[j] > a * b){
a = arr[i];
b = arr[j];
}
System.out.println("Max product pair is {" +
a + ", " + b + "}");
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = {1, 4, 3, 6, 7, 0};
int n = arr.length;
maxProduct(arr, n);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# A simple Python3 program to find max
# product pair in an array of integers
# Function to find maximum
# product pair in arr[0..n-1]
def maxProduct(arr, n):
if (n < 2):
print("No pairs exists")
return
# Initialize max product pair
a = arr[0]; b = arr[1]
# Traverse through every possible pair
# and keep track of max product
for i in range(0, n):
for j in range(i + 1, n):
if (arr[i] * arr[j] > a * b):
a = arr[i]; b = arr[j]
print("Max product pair is {", a, ",", b, "}",
sep = "")
# Driver Code
arr = [1, 4, 3, 6, 7, 0]
n = len(arr)
maxProduct(arr, n)
# This code is contributed by Smitha Dinesh Semwal.
C#
// C# Code to Find a pair with maximum
// product in array of Integers
using System;
class GFG
{
// Function to find maximum
// product pair in arr[0..n-1]
static void maxProduct(int []arr, int n)
{
if (n < 2)
{
Console.Write("No pairs exists");
return;
}
// Initialize max product pair
int a = arr[0], b = arr[1];
// Traverse through every possible pair
// and keep track of max product
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] * arr[j] > a * b)
{
a = arr[i];
b = arr[j];
}
Console.Write("Max product pair is {" +
a + ", " + b + "}");
}
// Driver Code
public static void Main()
{
int []arr = {1, 4, 3, 6, 7, 0};
int n = arr.Length;
maxProduct(arr, n);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A simple PHP program to
// find max product pair in
// an array of integers
// Function to find maximum
// product pair in arr[0..n-1]
function maxProduct( $arr, $n)
{
if ($n < 2)
{
echo "No pairs exists\n";
return;
}
// Initialize max product pair
$a = $arr[0];
$b = $arr[1];
// Traverse through every possible pair
// and keep track of max product
for ($i = 0; $i < $n; $i++)
for ($j = $i + 1; $j < $n; $j++)
{
if ($arr[$i] * $arr[$j] > $a * $b)
{
$a = $arr[$i];
$b = $arr[$j];
}
}
echo "Max product pair is {" , $a , ", ";
echo $b , "}";
}
// Driver Code
$arr = array(1, 4, 3, 6, 7, 0);
$n = count($arr);
maxProduct($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// A simple Javascript program to find max product pair in
// an array of integers
// Function to find maximum product pair in arr[0..n-1]
function maxProduct(arr, n)
{
if (n < 2)
{
document.write("No pairs exists" + "<br>");
return;
}
// Initialize max product pair
let a = arr[0], b = arr[1];
// Traverse through every possible pair
// and keep track of max product
for (let i=0; i<n; i++)
for (let j=i+1; j<n; j++)
if (arr[i]*arr[j] > a*b)
a = arr[i], b = arr[j];
document.write("Max product pair is {" + a + ", "
+ b + "}");
}
// Driver program to test
let arr = [1, 4, 3, 6, 7, 0];
let n = arr.length;
maxProduct(arr, n);
// This code is contributed by Mayank Tyagi
</script>
Producción
Max product pair is {6, 7}
Complejidad del tiempo : O(n 2 )
Mejor enfoque:
Una mejor solución es utilizar la clasificación. A continuación se detallan los pasos.
- Ordene la array de entrada en orden creciente.
- Si todos los elementos son positivos, devuelva el producto de los dos últimos números.
- De lo contrario, devuelva un máximo de productos de los dos primeros y los dos últimos números.
Gracias a Rahul Jain por sugerir este método.
C++14
// C++ code to find a pair with maximum
// product in array of Integers
#include<bits/stdc++.h>
using namespace std;
void maxProduct(vector<int>arr, int n)
{
// Sort the array
sort(arr.begin(), arr.end());
int num1, num2;
// Calculate product of two smallest numbers
int sum1 = arr[0] * arr[1];
// Calculate product of two largest numbers
int sum2 = arr[n - 1] * arr[n - 2];
// Print the pairs whose product is greater
if (sum1 > sum2)
{
num1 = arr[0];
num2 = arr[1];
}
else
{
num1 = arr[n - 2];
num2 = arr[n - 1];
}
cout << ("Max product pair = ")
<< num1 << "," << num2;
}
// Driver Code
int main()
{
vector<int>arr = { 1, 4, 3, 6, 7, 0 };
int n = arr.size();
maxProduct(arr, n);
}
// This code is contributed by Stream_Cipher
Java
// JAVA Code to Find a pair with maximum
// product in array of Integers
import java.util.*;
public class GFG {
static void maxProduct(int arr[], int n)
{
// Sort the array
Arrays.sort(arr);
int num1, num2;
// Calculate product of two smallest numbers
int sum1 = arr[0] * arr[1];
// Calculate product of two largest numbers
int sum2 = arr[n - 1] * arr[n - 2];
// print the pairs whose product is greater
if (sum1 > sum2) {
num1 = arr[0];
num2 = arr[1];
}
else {
num1 = arr[n - 2];
num2 = arr[n - 1];
}
System.out.println("Max product pair = " +
"{" + num1 + "," + num2 + "}");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 4, 3, 6, 7, 0 };
int n = arr.length;
maxProduct(arr, n);
}
}
// Contributed by Navtika Kumar
Python3
# Python code to find a pair with maximum
# product in array of Integers
def maxProduct(arr, n):
# Sort the array
arr.sort()
num1 = num2 = 0
# Calculate product of two smallest numbers
sum1 = arr[0] * arr[1]
# Calculate product of two largest numbers
sum2 = arr[n - 1] * arr[n - 2]
# Print the pairs whose product is greater
if (sum1 > sum2):
num1 = arr[0]
num2 = arr[1]
else:
num1 = arr[n - 2]
num2 = arr[n - 1]
print("Max product pair = {", num1, ",", num2, "}", sep="")
# Driver Code
arr = [1, 4, 3, 6, 7, 0]
n = len(arr)
maxProduct(arr, n)
# This code is contributed by subhammahato348.
C#
// C# code to Find a pair with maximum
// product in array of Integers
using System;
class GFG{
static void maxProduct(int []arr, int n)
{
// Sort the array
Array.Sort(arr);
int num1, num2;
// Calculate product of two
// smallest numbers
int sum1 = arr[0] * arr[1];
// Calculate product of two
// largest numbers
int sum2 = arr[n - 1] * arr[n - 2];
// Print the pairs whose
// product is greater
if (sum1 > sum2)
{
num1 = arr[0];
num2 = arr[1];
}
else
{
num1 = arr[n - 2];
num2 = arr[n - 1];
}
Console.Write("Max product pair = " +
"{" + num1 + "," + num2 + "}");
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 4, 3, 6, 7, 0 };
int n = arr.Length;
maxProduct(arr, n);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript code to Find a pair with maximum
// product in array of Integers
function maxProduct(arr, n)
{
// Sort the array
arr.sort(function(a, b){return a - b});
let num1, num2;
// Calculate product of two smallest numbers
let sum1 = arr[0] * arr[1];
// Calculate product of two largest numbers
let sum2 = arr[n - 1] * arr[n - 2];
// print the pairs whose product is greater
if (sum1 > sum2)
{
num1 = arr[0];
num2 = arr[1];
}
else
{
num1 = arr[n - 2];
num2 = arr[n - 1];
}
document.write("Max product pair = " +
"{" + num1 + "," + num2 + "}");
}
// Driver Code
let arr = [ 1, 4, 3, 6, 7, 0 ];
let n = arr.length;
maxProduct(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Max product pair = 6,7
Complejidad temporal: O(nlog n)
Espacio auxiliar: O(1)
Enfoque eficiente:
Una solución eficiente puede resolver el problema anterior en un solo recorrido de la array de entrada. La idea es recorrer la array de entrada y realizar un seguimiento de los siguientes cuatro valores.
- Valor positivo máximo
- Segundo valor máximo positivo
- Valor negativo máximo, es decir, un valor negativo con valor absoluto máximo
- Segundo valor máximo negativo.
Al final del ciclo, compare los productos de los dos primeros y los dos últimos e imprima el máximo de dos productos. A continuación se muestra la implementación de esta idea.
C++
// A O(n) C++ program to find maximum product pair in an array
#include<bits/stdc++.h>
using namespace std;
// Function to find maximum product pair in arr[0..n-1]
void maxProduct(int arr[], int n)
{
if (n < 2)
{
cout << "No pairs exists\n";
return;
}
if (n == 2)
{
cout << arr[0] << " " << arr[1] << endl;
return;
}
// Initialize maximum and second maximum
int posa = INT_MIN, posb = INT_MIN;
// Initialize minimum and second minimum
int nega = INT_MIN, negb = INT_MIN;
// Traverse given array
for (int i = 0; i < n; i++)
{
// Update maximum and second maximum if needed
if (arr[i] > posa)
{
posb = posa;
posa = arr[i];
}
else if (arr[i] > posb)
posb = arr[i];
// Update minimum and second minimum if needed
if (arr[i] < 0 && abs(arr[i]) > abs(nega))
{
negb = nega;
nega = arr[i];
}
else if(arr[i] < 0 && abs(arr[i]) > abs(negb))
negb = arr[i];
}
if (nega*negb > posa*posb)
cout << "Max product pair is {" << nega << ", "
<< negb << "}";
else
cout << "Max product pair is {" << posa << ", "
<< posb << "}";
}
// Driver program to test above function
int main()
{
int arr[] = {1, 4, 3, 6, 7, 0};
int n = sizeof(arr)/sizeof(arr[0]);
maxProduct(arr, n);
return 0;
}
Java
// JAVA Code to Find a pair with maximum
// product in array of Integers
import java.util.*;
class GFG {
// Function to find maximum product pair
// in arr[0..n-1]
static void maxProduct(int arr[], int n)
{
if (n < 2)
{
System.out.println("No pairs exists");
return;
}
if (n == 2)
{
System.out.println(arr[0] + " " + arr[1]);
return;
}
// Initialize maximum and second maximum
int posa = Integer.MIN_VALUE,
posb = Integer.MIN_VALUE;
// Initialize minimum and second minimum
int nega = Integer.MIN_VALUE,
negb = Integer.MIN_VALUE;
// Traverse given array
for (int i = 0; i < n; i++)
{
// Update maximum and second maximum
// if needed
if (arr[i] > posa)
{
posb = posa;
posa = arr[i];
}
else if (arr[i] > posb)
posb = arr[i];
// Update minimum and second minimum
// if needed
if (arr[i] < 0 && Math.abs(arr[i]) >
Math.abs(nega))
{
negb = nega;
nega = arr[i];
}
else if(arr[i] < 0 && Math.abs(arr[i])
> Math.abs(negb))
negb = arr[i];
}
if (nega * negb > posa * posb)
System.out.println("Max product pair is {"
+ nega + ", " + negb + "}");
else
System.out.println("Max product pair is {"
+ posa + ", " + posb + "}");
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = {1, 4, 3, 6, 7, 0};
int n = arr.length;
maxProduct(arr, n);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# A O(n) Python 3 program to find
# maximum product pair in an array
# Function to find maximum product
# pair in arr[0..n-1]
def maxProduct(arr, n):
if (n < 2):
print("No pairs exists")
return
if (n == 2):
print(arr[0] ," " , arr[1])
return
# Initialize maximum and
# second maximum
posa = 0
posb = 0
# Initialize minimum and
# second minimum
nega = 0
negb = 0
# Traverse given array
for i in range(n):
# Update maximum and second
# maximum if needed
if (arr[i] > posa):
posb = posa
posa = arr[i]
elif (arr[i] > posb):
posb = arr[i]
# Update minimum and second
# minimum if needed
if (arr[i] < 0 and abs(arr[i]) > abs(nega)):
negb = nega
nega = arr[i]
elif(arr[i] < 0 and abs(arr[i]) > abs(negb)):
negb = arr[i]
if (nega * negb > posa * posb):
print("Max product pair is {" ,
nega ,", ", negb , "}")
else:
print( "Max product pair is {" ,
posa ,", " ,posb , "}")
# Driver Code
if __name__ =="__main__":
arr = [1, 4, 3, 6, 7, 0]
n = len(arr)
maxProduct(arr, n)
# This code is contributed
# by ChitraNayal
C#
// C# Code to Find a pair with maximum
// product in array of Integers
using System;
class GFG {
// Function to find maximum
// product pair in arr[0..n-1]
static void maxProduct(int []arr, int n)
{
if (n < 2)
{
Console.WriteLine("No pairs exists");
return;
}
if (n == 2)
{
Console.WriteLine(arr[0] + " " + arr[1]);
return;
}
// Initialize maximum and
// second maximum
int posa = int.MinValue;
int posb = int.MaxValue;
// Initialize minimum and
// second minimum
int nega = int.MinValue;
int negb = int.MaxValue;
// Traverse given array
for (int i = 0; i < n; i++)
{
// Update maximum and
// second maximum
// if needed
if (arr[i] > posa)
{
posb = posa;
posa = arr[i];
}
else if (arr[i] > posb)
posb = arr[i];
// Update minimum and
// second minimum if
// needed
if (arr[i] < 0 && Math.Abs(arr[i]) >
Math.Abs(nega))
{
negb = nega;
nega = arr[i];
}
else if(arr[i] < 0 &&
Math.Abs(arr[i]) >
Math.Abs(negb))
negb = arr[i];
}
if (nega * negb > posa * posb)
Console.WriteLine("Max product pair is {"
+ nega + ", " + negb + "}");
else
Console.WriteLine("Max product pair is {"
+ posa + ", " + posb + "}");
}
// Driver Code
public static void Main()
{
int []arr = {1, 4, 3, 6, 7, 0};
int n = arr.Length;
maxProduct(arr, n);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// A O(n) PHP program to find maximum
// product pair in an array
// Function to find maximum product
// pair in arr[0..n-1]
function maxProduct(&$arr, $n)
{
if ($n < 2)
{
echo("No pairs exists\n");
return;
}
if ($n == 2)
{
echo ($arr[0]);
echo (" ");
echo($arr[1]);
echo("\n");
return;
}
// Initialize maximum and
// second maximum
$posa = 0;
$posb = 0;
// Initialize minimum and
// second minimum
$nega = 0;
$negb = 0;
// Traverse given array
for ($i = 0; $i < $n; $i++)
{
// Update maximum and second
// maximum if needed
if ($arr[$i] > $posa)
{
$posb = $posa;
$posa = $arr[$i];
}
else if ($arr[$i] > $posb)
$posb = $arr[$i];
// Update minimum and second
// minimum if needed
if ($arr[$i] < 0 &&
abs($arr[$i]) > abs($nega))
{
$negb = $nega;
$nega = $arr[$i];
}
else if($arr[$i] < 0 &&
abs($arr[$i]) > abs($negb))
$negb = $arr[$i];
}
if ($nega * $negb > $posa * $posb)
{
echo("Max product pair is {");
echo $nega;
echo(", ");
echo ($negb);
echo ("}");
}
else
{
echo("Max product pair is {");
echo $posa;
echo(", ");
echo ($posb);
echo ("}");
}
}
// Driver Code
$arr = array(1, 4, 3, 6, 7, 0);
$n = sizeof($arr);
maxProduct($arr, $n);
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// JAVAscript Code to Find a pair with maximum
// product in array of Integers
// Function to find maximum product pair
// in arr[0..n-1]
function maxProduct(arr,n)
{
if (n < 2)
{
document.write("No pairs exists");
return;
}
if (n == 2)
{
document.write(arr[0] + " " + arr[1]);
return;
}
// Initialize maximum and second maximum
let posa = Number.MIN_VALUE,
posb = Number.MIN_VALUE;
// Initialize minimum and second minimum
let nega = Number.MIN_VALUE,
negb = Number.MIN_VALUE;
// Traverse given array
for (let i = 0; i < n; i++)
{
// Update maximum and second maximum
// if needed
if (arr[i] > posa)
{
posb = posa;
posa = arr[i];
}
else if (arr[i] > posb)
posb = arr[i];
// Update minimum and second minimum
// if needed
if (arr[i] < 0 && Math.abs(arr[i]) >
Math.abs(nega))
{
negb = nega;
nega = arr[i];
}
else if(arr[i] < 0 && Math.abs(arr[i])
> Math.abs(negb))
negb = arr[i];
}
if (nega * negb > posa * posb)
document.write("Max product pair is {"
+ nega + ", " + negb + "}");
else
document.write("Max product pair is {"
+ posa + ", " + posb + "}");
}
/* Driver program to test above function */
let arr=[1, 4, 3, 6, 7, 0];
let n = arr.length;
maxProduct(arr, n);
// This code is contributed by rag2127
</script>
Producción
Max product pair is {7, 6}
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
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