Dada una array de enteros, encuentre un producto máximo de un triplete en la array.
Ejemplos:
Input: [10, 3, 5, 6, 20] Output: 1200 Multiplication of 10, 6 and 20 Input: [-10, -3, -5, -6, -20] Output: -90 Input: [1, -4, 3, -6, 7, 0] Output: 168
Enfoque 1 (Ingenuo, O(n 3 ) tiempo, O(1) Espacio)
Una solución simple es verificar cada triplete usando tres bucles anidados. A continuación se muestra su implementación:
C++
// A C++ program to find a maximum product of a
// triplet in array of integers
#include <bits/stdc++.h>
using namespace std;
/* Function to find a maximum product of a triplet
in array of integers of size n */
int maxProduct(int arr[], int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// will contain max product
int max_product = INT_MIN;
for (int i = 0; i < n - 2; i++)
for (int j = i + 1; j < n - 1; j++)
for (int k = j + 1; k < n; k++)
max_product = max(max_product,
arr[i] * arr[j] * arr[k]);
return max_product;
}
// Driver program to test above functions
int main()
{
int arr[] = { 10, 3, 5, 6, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = maxProduct(arr, n);
if (max == -1)
cout << "No Triplet Exists";
else
cout << "Maximum product is " << max;
return 0;
}
Java
// A Java program to find a
// maximum product of a
// triplet in array of integers
class GFG {
// Function to find a maximum
// product of a triplet in array
// of integers of size n
static int maxProduct(int []arr, int n)
{
// if size is less than
// 3, no triplet exists
if (n < 3)
return -1;
// will contain max product
int max_product = Integer.MIN_VALUE;
for (int i = 0; i < n - 2; i++)
for (int j = i + 1; j < n - 1; j++)
for (int k = j + 1; k < n; k++)
max_product = Math.max(max_product,
arr[i] * arr[j] * arr[k]);
return max_product;
}
// Driver Code
public static void main (String [] args)
{
int []arr = { 10, 3, 5, 6, 20 };
int n = arr.length;;
int max = maxProduct(arr, n);
if (max == -1)
System.out.println("No Triplet Exists");
else
System.out.println("Maximum product is " + max);
}
}
Python3
# Python3 program to find a maximum
# product of a triplet in array
# of integers
import sys
# Function to find a maximum
# product of a triplet in array
# of integers of size n
def maxProduct(arr, n):
# if size is less than 3,
# no triplet exists
if n < 3:
return -1
# will contain max product
max_product = -(sys.maxsize - 1)
for i in range(0, n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
max_product = max(
max_product, arr[i]
* arr[j] * arr[k])
return max_product
# Driver Program
arr = [10, 3, 5, 6, 20]
n = len(arr)
max = maxProduct(arr, n)
if max == -1:
print("No Tripplet Exits")
else:
print("Maximum product is", max)
# This code is contributed by Shrikant13
C#
// A C# program to find a
// maximum product of a
// triplet in array of integers
using System;
class GFG {
// Function to find a maximum
// product of a triplet in array
// of integers of size n
static int maxProduct(int []arr, int n)
{
// if size is less than
// 3, no triplet exists
if (n < 3)
return -1;
// will contain max product
int max_product = int.MinValue;
for (int i = 0; i < n - 2; i++)
for (int j = i + 1; j < n - 1; j++)
for (int k = j + 1; k < n; k++)
max_product = Math.Max(max_product,
arr[i] * arr[j] * arr[k]);
return max_product;
}
// Driver Code
public static void Main ()
{
int []arr = { 10, 3, 5, 6, 20 };
int n = arr.Length;;
int max = maxProduct(arr, n);
if (max == -1)
Console.WriteLine("No Triplet Exists");
else
Console.WriteLine("Maximum product is " + max);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// A PHP program to find a
// maximum product of a
// triplet in array of integers
// Function to find a maximum
// product of a triplet
// in array of integers of
// size n
function maxProduct($arr, $n)
{
$INT_MIN = 0;
// if size is less than
// 3, no triplet exists
if ($n < 3)
return -1;
// will contain max product
$max_product = $INT_MIN;
for ($i = 0; $i < $n - 2; $i++)
for ($j = $i + 1; $j < $n - 1; $j++)
for ($k = $j + 1; $k < $n; $k++)
$max_product = max($max_product,
$arr[$i] * $arr[$j] * $arr[$k]);
return $max_product;
}
// Driver Code
$arr = array(10, 3, 5, 6, 20 );
$n = sizeof($arr);
$max = maxProduct($arr, $n);
if ($max == -1)
echo "No Triplet Exists";
else
echo "Maximum product is " ,$max;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// JavaScript program to find a
// maximum product of a
// triplet in array of integers
// Function to find a maximum
// product of a triplet in array
// of integers of size n
function maxProduct(arr, n)
{
// if size is less than
// 3, no triplet exists
if (n < 3)
return -1;
// will contain max product
let max_product = Number.MIN_VALUE;
for (let i = 0; i < n - 2; i++)
for (let j = i + 1; j < n - 1; j++)
for (let k = j + 1; k < n; k++)
max_product = Math.max(max_product,
arr[i] * arr[j] * arr[k]);
return max_product;
}
// Driver Code
let arr = [ 10, 3, 5, 6, 20 ];
let n = arr.length;;
let max = maxProduct(arr, n);
if (max == -1)
document.write("No Triplet Exists");
else
document.write("Maximum product is " + max);
</script>
Producción :
Maximum product is 1200
Enfoque 2: O(n) Tiempo, O(n) Espacio
- Construya cuatro arrays auxiliares leftMax[], rightMax[], leftMin[] y rightMin[] del mismo tamaño que la array de entrada.
- Rellene leftMax[], rightMax[], leftMin[] y rightMin[] de la siguiente manera.
- leftMax[i] contendrá el elemento máximo a la izquierda de arr[i] excluyendo arr[i]. Para el índice 0, la izquierda contendrá -1.
- leftMin[i] contendrá el elemento mínimo a la izquierda de arr[i] excluyendo arr[i]. Para el índice 0, la izquierda contendrá -1.
- rightMax[i] contendrá el elemento máximo a la derecha de arr[i] excluyendo arr[i]. Para el índice n-1, la derecha contendrá -1.
- rightMin[i] contendrá el elemento mínimo a la derecha de arr[i] excluyendo arr[i]. Para el índice n-1, la derecha contendrá -1.
- Para todos los índices de array i excepto el primero y el último índice, calcule el máximo de arr[i]*x*y donde x puede ser leftMax[i] o leftMin[i] e y puede ser rightMax[i] o rightMin[i].
- Devuelve el máximo del paso 3.
A continuación se muestra su implementación:
C++
// A C++ program to find a maximum product of a triplet
// in array of integers
#include <bits/stdc++.h>
using namespace std;
/* Function to find a maximum product of a triplet
in array of integers of size n */
int maxProduct(int arr[], int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Construct four auxiliary vectors
// of size n and initialize them by -1
vector<int> leftMin(n, -1);
vector<int> rightMin(n, -1);
vector<int> leftMax(n, -1);
vector<int> rightMax(n, -1);
// will contain max product
int max_product = INT_MIN;
// to store maximum element on left of array
int max_sum = arr[0];
// to store minimum element on left of array
int min_sum = arr[0];
// leftMax[i] will contain max element
// on left of arr[i] excluding arr[i].
// leftMin[i] will contain min element
// on left of arr[i] excluding arr[i].
for (int i = 1; i < n; i++)
{
leftMax[i] = max_sum;
if (arr[i] > max_sum)
max_sum = arr[i];
leftMin[i] = min_sum;
if (arr[i] < min_sum)
min_sum = arr[i];
}
// reset max_sum to store maximum element on
// right of array
max_sum = arr[n - 1];
// reset min_sum to store minimum element on
// right of array
min_sum = arr[n - 1];
// rightMax[i] will contain max element
// on right of arr[i] excluding arr[i].
// rightMin[i] will contain min element
// on right of arr[i] excluding arr[i].
for (int j = n - 2; j >= 0; j--)
{
rightMax[j] = max_sum;
if (arr[j] > max_sum)
max_sum = arr[j];
rightMin[j] = min_sum;
if (arr[j] < min_sum)
min_sum = arr[j];
}
// For all array indexes i except first and
// last, compute maximum of arr[i]*x*y where
// x can be leftMax[i] or leftMin[i] and
// y can be rightMax[i] or rightMin[i].
for (int i = 1; i < n - 1; i++)
{
int max1 = max(arr[i] * leftMax[i] * rightMax[i],
arr[i] * leftMin[i] * rightMin[i]);
int max2 = max(arr[i] * leftMax[i] * rightMin[i],
arr[i] * leftMin[i] * rightMax[i]);
max_product = max(max_product, max(max1, max2));
}
return max_product;
}
// Driver program to test above functions
int main()
{
int arr[] = { 1, 4, 3, -6, -7, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = maxProduct(arr, n);
if (max == -1)
cout << "No Triplet Exists";
else
cout << "Maximum product is " << max;
return 0;
}
Java
// A Java program to find a maximum product of a triplet
// in array of integers
import java.util.*;
class GFG
{
/* Function to find a maximum product of a triplet
in array of integers of size n */
static int maxProduct(int []arr, int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Construct four auxiliary vectors
// of size n and initialize them by -1
int[] leftMin = new int[n];
int[] rightMin = new int[n];
int[] leftMax = new int[n];
int[] rightMax = new int[n];
Arrays.fill(leftMin, -1);
Arrays.fill(leftMax, -1);
Arrays.fill(rightMax, -1);
Arrays.fill(rightMin, -1);
// will contain max product
int max_product = Integer.MIN_VALUE;
// to store maximum element on left of array
int max_sum = arr[0];
// to store minimum element on left of array
int min_sum = arr[0];
// leftMax[i] will contain max element
// on left of arr[i] excluding arr[i].
// leftMin[i] will contain min element
// on left of arr[i] excluding arr[i].
for (int i = 1; i < n; i++)
{
leftMax[i] = max_sum;
if (arr[i] > max_sum)
max_sum = arr[i];
leftMin[i] = min_sum;
if (arr[i] < min_sum)
min_sum = arr[i];
}
// reset max_sum to store maximum element on
// right of array
max_sum = arr[n - 1];
// reset min_sum to store minimum element on
// right of array
min_sum = arr[n - 1];
// rightMax[i] will contain max element
// on right of arr[i] excluding arr[i].
// rightMin[i] will contain min element
// on right of arr[i] excluding arr[i].
for (int j = n - 2; j >= 0; j--)
{
rightMax[j] = max_sum;
if (arr[j] > max_sum)
max_sum = arr[j];
rightMin[j] = min_sum;
if (arr[j] < min_sum)
min_sum = arr[j];
}
// For all array indexes i except first and
// last, compute maximum of arr[i]*x*y where
// x can be leftMax[i] or leftMin[i] and
// y can be rightMax[i] or rightMin[i].
for (int i = 1; i < n - 1; i++)
{
int max1 = Math.max(arr[i] * leftMax[i] * rightMax[i],
arr[i] * leftMin[i] * rightMin[i]);
int max2 = Math.max(arr[i] * leftMax[i] * rightMin[i],
arr[i] * leftMin[i] * rightMax[i]);
max_product = Math.max(max_product, Math.max(max1, max2));
}
return max_product;
}
// Driver code
public static void main (String[] args)
{
int []arr = { 1, 4, 3, -6, -7, 0 };
int n = arr.length;
int max = maxProduct(arr, n);
if (max == -1)
System.out.println("No Triplet Exists");
else
System.out.println("Maximum product is "+max);
}
}
// This code is contributed by mits
Python3
# A Python3 program to find a maximum product
# of a triplet in array of integers
import sys
# Function to find a maximum product of a
# triplet in array of integers of size n
def maxProduct(arr, n):
# If size is less than 3, no triplet exists
if (n < 3):
return -1
# Construct four auxiliary vectors
# of size n and initialize them by -1
leftMin = [-1 for i in range(n)]
rightMin = [-1 for i in range(n)]
leftMax = [-1 for i in range(n)]
rightMax = [-1 for i in range(n)]
# Will contain max product
max_product = -sys.maxsize - 1
# To store maximum element on
# left of array
max_sum = arr[0]
# To store minimum element on
# left of array
min_sum = arr[0]
# leftMax[i] will contain max element
# on left of arr[i] excluding arr[i].
# leftMin[i] will contain min element
# on left of arr[i] excluding arr[i].
for i in range(1, n):
leftMax[i] = max_sum
if (arr[i] > max_sum):
max_sum = arr[i]
leftMin[i] = min_sum
if (arr[i] < min_sum):
min_sum = arr[i]
# Reset max_sum to store maximum
# element on right of array
max_sum = arr[n - 1]
# Reset min_sum to store minimum
# element on right of array
min_sum = arr[n - 1]
# rightMax[i] will contain max element
# on right of arr[i] excluding arr[i].
# rightMin[i] will contain min element
# on right of arr[i] excluding arr[i].
for j in range(n - 2, -1, -1):
rightMax[j] = max_sum
if (arr[j] > max_sum):
max_sum = arr[j]
rightMin[j] = min_sum
if (arr[j] < min_sum):
min_sum = arr[j]
# For all array indexes i except first and
# last, compute maximum of arr[i]*x*y where
# x can be leftMax[i] or leftMin[i] and
# y can be rightMax[i] or rightMin[i].
for i in range(1, n - 1):
max1 = max(arr[i] * leftMax[i] * rightMax[i],
arr[i] * leftMin[i] * rightMin[i])
max2 = max(arr[i] * leftMax[i] * rightMin[i],
arr[i] * leftMin[i] * rightMax[i])
max_product = max(max_product, max(max1, max2))
return max_product
# Driver code
arr = [ 1, 4, 3, -6, -7, 0 ]
n = len(arr)
Max = maxProduct(arr, n)
if (Max == -1):
print("No Triplet Exists")
else:
print("Maximum product is", Max)
# This code is contributed by rag2127
C#
// A C# program to find a maximum product of a triplet
// in array of integers
using System;
class GFG
{
/* Function to find a maximum product of a triplet
in array of integers of size n */
static int maxProduct(int []arr, int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Construct four auxiliary vectors
// of size n and initialize them by -1
int[] leftMin=new int[n];
int[] rightMin=new int[n];
int[] leftMax=new int[n];
int[] rightMax=new int[n];
Array.Fill(leftMin,-1);
Array.Fill(leftMax,-1);
Array.Fill(rightMax,-1);
Array.Fill(rightMin,-1);
// will contain max product
int max_product = int.MinValue;
// to store maximum element on left of array
int max_sum = arr[0];
// to store minimum element on left of array
int min_sum = arr[0];
// leftMax[i] will contain max element
// on left of arr[i] excluding arr[i].
// leftMin[i] will contain min element
// on left of arr[i] excluding arr[i].
for (int i = 1; i < n; i++)
{
leftMax[i] = max_sum;
if (arr[i] > max_sum)
max_sum = arr[i];
leftMin[i] = min_sum;
if (arr[i] < min_sum)
min_sum = arr[i];
}
// reset max_sum to store maximum element on
// right of array
max_sum = arr[n - 1];
// reset min_sum to store minimum element on
// right of array
min_sum = arr[n - 1];
// rightMax[i] will contain max element
// on right of arr[i] excluding arr[i].
// rightMin[i] will contain min element
// on right of arr[i] excluding arr[i].
for (int j = n - 2; j >= 0; j--)
{
rightMax[j] = max_sum;
if (arr[j] > max_sum)
max_sum = arr[j];
rightMin[j] = min_sum;
if (arr[j] < min_sum)
min_sum = arr[j];
}
// For all array indexes i except first and
// last, compute maximum of arr[i]*x*y where
// x can be leftMax[i] or leftMin[i] and
// y can be rightMax[i] or rightMin[i].
for (int i = 1; i < n - 1; i++)
{
int max1 = Math.Max(arr[i] * leftMax[i] * rightMax[i],
arr[i] * leftMin[i] * rightMin[i]);
int max2 = Math.Max(arr[i] * leftMax[i] * rightMin[i],
arr[i] * leftMin[i] * rightMax[i]);
max_product = Math.Max(max_product, Math.Max(max1, max2));
}
return max_product;
}
// Driver code
static void Main()
{
int []arr = { 1, 4, 3, -6, -7, 0 };
int n = arr.Length;
int max = maxProduct(arr, n);
if (max == -1)
Console.WriteLine("No Triplet Exists");
else
Console.WriteLine("Maximum product is "+max);
}
}
// This code is contributed by mits
PHP
<?php
// A PHP program to find a maximum product of a triplet
// in array of integers
/* Function to find a maximum product of a triplet
in array of integers of size n */
function maxProduct($arr, $n)
{
// if size is less than 3, no triplet exists
if ($n < 3)
return -1;
// Construct four auxiliary vectors
// of size n and initialize them by -1
$leftMin=array_fill(0,$n, -1);
$rightMin=array_fill(0,$n, -1);
$leftMax=array_fill(0,$n, -1);
$rightMax=array_fill(0,$n, -1);
// will contain max product
$max_product = PHP_INT_MIN;
// to store maximum element on left of array
$max_sum = $arr[0];
// to store minimum element on left of array
$min_sum = $arr[0];
// leftMax[i] will contain max element
// on left of arr[i] excluding arr[i].
// leftMin[i] will contain min element
// on left of arr[i] excluding arr[i].
for ($i = 1; $i < $n; $i++)
{
$leftMax[$i] = $max_sum;
if ($arr[$i] > $max_sum)
$max_sum = $arr[$i];
$leftMin[$i] = $min_sum;
if ($arr[$i] < $min_sum)
$min_sum = $arr[$i];
}
// reset max_sum to store maximum element on
// right of array
$max_sum = $arr[$n - 1];
// reset min_sum to store minimum element on
// right of array
$min_sum = $arr[$n - 1];
// rightMax[i] will contain max element
// on right of arr[i] excluding arr[i].
// rightMin[i] will contain min element
// on right of arr[i] excluding arr[i].
for ($j = $n - 2; $j >= 0; $j--)
{
$rightMax[$j] = $max_sum;
if ($arr[$j] > $max_sum)
$max_sum = $arr[$j];
$rightMin[$j] = $min_sum;
if ($arr[$j] < $min_sum)
$min_sum = $arr[$j];
}
// For all array indexes i except first and
// last, compute maximum of arr[i]*x*y where
// x can be leftMax[i] or leftMin[i] and
// y can be rightMax[i] or rightMin[i].
for ($i = 1; $i < $n - 1; $i++)
{
$max1 = max($arr[$i] * $leftMax[$i] * $rightMax[$i],
$arr[$i] * $leftMin[$i] * $rightMin[$i]);
$max2 = max($arr[$i] * $leftMax[$i] * $rightMin[$i],
$arr[$i] * $leftMin[$i] * $rightMax[$i]);
$max_product = max($max_product, max($max1, $max2));
}
return $max_product;
}
// Driver program to test above functions
$arr = array( 1, 4, 3, -6, -7, 0 );
$n = count($arr);
$max = maxProduct($arr, $n);
if ($max == -1)
echo "No Triplet Exists";
else
echo "Maximum product is ".$max;
// This code is contributed by mits
?>
Javascript
<script>
// A javascript program to find a maximum product of a triplet
// in array of integers
/* Function to find a maximum product of a triplet
in array of integers of size n */
function maxProduct(arr , n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Construct four auxiliary vectors
// of size n and initialize them by -1
leftMin = Array.from({length: n}, (_, i) => -1);
rightMin = Array.from({length: n}, (_, i) => -1);
leftMax = Array.from({length: n}, (_, i) => -1);
rightMax = Array.from({length: n}, (_, i) => -1);
// will contain max product
var max_product = Number.MIN_VALUE;
// to store maximum element on left of array
var max_sum = arr[0];
// to store minimum element on left of array
var min_sum = arr[0];
// leftMax[i] will contain max element
// on left of arr[i] excluding arr[i].
// leftMin[i] will contain min element
// on left of arr[i] excluding arr[i].
for (i = 1; i < n; i++)
{
leftMax[i] = max_sum;
if (arr[i] > max_sum)
max_sum = arr[i];
leftMin[i] = min_sum;
if (arr[i] < min_sum)
min_sum = arr[i];
}
// reset max_sum to store maximum element on
// right of array
max_sum = arr[n - 1];
// reset min_sum to store minimum element on
// right of array
min_sum = arr[n - 1];
// rightMax[i] will contain max element
// on right of arr[i] excluding arr[i].
// rightMin[i] will contain min element
// on right of arr[i] excluding arr[i].
for (j = n - 2; j >= 0; j--)
{
rightMax[j] = max_sum;
if (arr[j] > max_sum)
max_sum = arr[j];
rightMin[j] = min_sum;
if (arr[j] < min_sum)
min_sum = arr[j];
}
// For all array indexes i except first and
// last, compute maximum of arr[i]*x*y where
// x can be leftMax[i] or leftMin[i] and
// y can be rightMax[i] or rightMin[i].
for (i = 1; i < n - 1; i++)
{
var max1 = Math.max(arr[i] * leftMax[i] * rightMax[i],
arr[i] * leftMin[i] * rightMin[i]);
var max2 = Math.max(arr[i] * leftMax[i] * rightMin[i],
arr[i] * leftMin[i] * rightMax[i]);
max_product = Math.max(max_product, Math.max(max1, max2));
}
return max_product;
}
// Driver code
var arr = [ 1, 4, 3, -6, -7, 0 ];
var n = arr.length;
var max = maxProduct(arr, n);
if (max == -1)
document.write("No Triplet Exists");
else
document.write("Maximum product is "+max);
// This code is contributed by Amit Katiyar
</script>
Producción :
Maximum product is 168
Enfoque 3: O(nlogn) Tiempo, O(1) Espacio
- Ordene la array utilizando algún algoritmo de clasificación en el lugar eficiente en orden ascendente.
- Devuelve el máximo del producto de los últimos tres elementos de la array y el producto de los primeros dos elementos y el último elemento.
A continuación se muestra la implementación del enfoque anterior:
C++
// A C++ program to find a maximum product of a
// triplet in array of integers
#include <bits/stdc++.h>
using namespace std;
/* Function to find a maximum product of a triplet
in array of integers of size n */
int maxProduct(int arr[], int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Sort the array in ascending order
sort(arr, arr + n);
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3]);
}
// Driver program to test above functions
int main()
{
int arr[] = { -10, -3, 5, 6, -20 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = maxProduct(arr, n);
if (max == -1)
cout << "No Triplet Exists";
else
cout << "Maximum product is " << max;
return 0;
}
Java
// Java program to find a maximum product of a
// triplet in array of integers
import java.util.Arrays;
class GFG {
/* Function to find a maximum product of a triplet
in array of integers of size n */
static int maxProduct(int arr[], int n) {
// if size is less than 3, no triplet exists
if (n < 3) {
return -1;
}
// Sort the array in ascending order
Arrays.sort(arr);
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return Math.max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3]);
}
// Driver program to test above functions
public static void main(String[] args) {
int arr[] = {-10, -3, 5, 6, -20};
int n = arr.length;
int max = maxProduct(arr, n);
if (max == -1) {
System.out.println("No Triplet Exists");
} else {
System.out.println("Maximum product is " + max);
}
}
}
/* This Java code is contributed by Rajput-Ji*/
Python3
# A Python3 program to find a maximum
# product of a triplet in an array of integers
# Function to find a maximum product of a
# triplet in array of integers of size n
def maxProduct(arr, n):
# if size is less than 3, no triplet exists
if n < 3:
return -1
# Sort the array in ascending order
arr.sort()
# Return the maximum of product of last
# three elements and product of first
# two elements and last element
return max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3])
# Driver Code
if __name__ == "__main__":
arr = [-10, -3, 5, 6, -20]
n = len(arr)
_max = maxProduct(arr, n)
if _max == -1:
print("No Triplet Exists")
else:
print("Maximum product is", _max)
# This code is contributed by Rituraj Jain
C#
// C# program to find a maximum product of a
// triplet in array of integers
using System;
public class GFG {
/* Function to find a maximum product of a triplet
in array of integers of size n */
static int maxProduct(int []arr, int n) {
// if size is less than 3, no triplet exists
if (n < 3) {
return -1;
}
// Sort the array in ascending order
Array.Sort(arr);
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return Math.Max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3]);
}
// Driver program to test above functions
public static void Main() {
int []arr = {-10, -3, 5, 6, -20};
int n = arr.Length;
int max = maxProduct(arr, n);
if (max == -1) {
Console.WriteLine("No Triplet Exists");
} else {
Console.WriteLine("Maximum product is " + max);
}
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to find a maximum product of a
// triplet in array of integers
/* Function to find a maximum product of a triplet
in array of integers of size n */
function maxProduct($arr, $n)
// if size is less than 3, no triplet exists
{
if ($n < 3)
{
return -1;
}
// Sort the array in ascending order
sort($arr);
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return max($arr[0] * $arr[1] * $arr[$n - 1],
$arr[$n - 1] * $arr[$n - 2] * $arr[$n - 3]);
}
// Driver code
$arr = array(-10, -3, 5, 6, -20);
$n = sizeof($arr);
$max = maxProduct($arr, $n);
if ($max == -1)
{
echo("No Triplet Exists");
}
else
{
echo("Maximum product is " . $max);
}
/* This code is contributed by Code_Mech*/
Javascript
<script>
// Javascript program to find a maximum
// product of a triplet in array of integers
// Function to find a maximum product of a
// triplet in array of integers of size n
function maxProduct(arr, n)
{
// If size is less than 3, no
// triplet exists
if (n < 3)
{
return -1;
}
// Sort the array in ascending order
arr.sort();
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return Math.max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3]);
}
// Driver code
var arr = [-10, -3, 5, 6, -20];
var n = arr.length;
var max = maxProduct(arr, n);
if (max == -1)
{
document.write("No Triplet Exists");
}
else
{
document.write("Maximum product is " + max);
}
// This code is contributed by Rajput-Ji
</script>
Producción :
Maximum product is 1200
Enfoque 4: O(n) Tiempo, O(1) Espacio
- Escanee la array y calcule el máximo, el segundo máximo y el tercer elemento máximo presentes en la array.
- Escanee la array y calcule el mínimo y el segundo elemento mínimo presente en la array.
- Devuelve el máximo del producto de Máximo, segundo máximo y tercer máximo y producto de Mínimo, segundo mínimo y elemento Máximo.
Nota: el paso 1 y el paso 2 se pueden realizar en un solo recorrido de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// A O(n) C++ program to find maximum product pair in
// an array.
#include <bits/stdc++.h>
using namespace std;
/* Function to find a maximum product of a triplet
in array of integers of size n */
int maxProduct(int arr[], int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Initialize Maximum, second maximum and third
// maximum element
int maxA = INT_MIN, maxB = INT_MIN, maxC = INT_MIN;
// Initialize Minimum and second minimum element
int minA = INT_MAX, minB = INT_MAX;
for (int i = 0; i < n; i++)
{
// Update Maximum, second maximum and third
// maximum element
if (arr[i] > maxA)
{
maxC = maxB;
maxB = maxA;
maxA = arr[i];
}
// Update second maximum and third maximum element
else if (arr[i] > maxB)
{
maxC = maxB;
maxB = arr[i];
}
// Update third maximum element
else if (arr[i] > maxC)
maxC = arr[i];
// Update Minimum and second minimum element
if (arr[i] < minA)
{
minB = minA;
minA = arr[i];
}
// Update second minimum element
else if(arr[i] < minB)
minB = arr[i];
}
return max(minA * minB * maxA,
maxA * maxB * maxC);
}
// Driver program to test above function
int main()
{
int arr[] = { 1, -4, 3, -6, 7, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = maxProduct(arr, n);
if (max == -1)
cout << "No Triplet Exists";
else
cout << "Maximum product is " << max;
return 0;
}
Java
// A O(n) Java program to find maximum product
// pair in an array.
import java.util.*;
class GFG{
// Function to find a maximum product of
// a triplet in array of integers of size n
static int maxProduct(int []arr, int n)
{
// If size is less than 3, no triplet exists
if (n < 3)
return -1;
// Initialize Maximum, second maximum
// and third maximum element
int maxA = Integer.MAX_VALUE,
maxB = Integer.MAX_VALUE,
maxC = Integer.MAX_VALUE;
// Initialize Minimum and
// second minimum element
int minA = Integer.MIN_VALUE,
minB = Integer.MIN_VALUE;
for(int i = 0; i < n; i++)
{
// Update Maximum, second maximum
// and third maximum element
if (arr[i] > maxA)
{
maxC = maxB;
maxB = maxA;
maxA = arr[i];
}
// Update second maximum and
// third maximum element
else if (arr[i] > maxB)
{
maxC = maxB;
maxB = arr[i];
}
// Update third maximum element
else if (arr[i] > maxC)
maxC = arr[i];
// Update Minimum and second
// minimum element
if (arr[i] < minA)
{
minB = minA;
minA = arr[i];
}
// Update second minimum element
else if(arr[i] < minB)
minB = arr[i];
}
return Math.max(minA * minB * maxA,
maxA * maxB * maxC);
}
// Driver code
public static void main(String[] args)
{
int []arr = { 1, -4, 3, -6, 7, 0 };
int n = arr.length;
int max = maxProduct(arr, n);
if (max == -1)
System.out.print("No Triplet Exists");
else
System.out.print("Maximum product is " + max);
}
}
// This code is contributed by pratham76
Python3
# A O(n) Python3 program to find maximum
# product pair in an array.
import sys
# Function to find a maximum product
# of a triplet in array of integers
# of size n
def maxProduct(arr, n):
# If size is less than 3, no
# triplet exists
if (n < 3):
return -1
# Initialize Maximum, second
# maximum and third maximum
# element
maxA = -sys.maxsize - 1
maxB = -sys.maxsize - 1
maxC = -sys.maxsize - 1
# Initialize Minimum and
# second minimum element
minA = sys.maxsize
minB = sys.maxsize
for i in range(n):
# Update Maximum, second
# maximum and third maximum
# element
if (arr[i] > maxA):
maxC = maxB
maxB = maxA
maxA = arr[i]
# Update second maximum and
# third maximum element
else if (arr[i] > maxB):
maxC = maxB
maxB = arr[i]
# Update third maximum element
else if (arr[i] > maxC):
maxC = arr[i]
# Update Minimum and second
# minimum element
if (arr[i] < minA):
minB = minA
minA = arr[i]
# Update second minimum element
else if (arr[i] < minB):
minB = arr[i]
return max(minA * minB * maxA,
maxA * maxB * maxC)
# Driver Code
arr = [ 1, -4, 3, -6, 7, 0 ]
n = len(arr)
Max = maxProduct(arr, n)
if (Max == -1):
print("No Triplet Exists")
else:
print("Maximum product is", Max)
# This code is contributed by avanitrachhadiya2155
C#
// A O(n) C# program to find maximum product
// pair in an array.
using System;
using System.Collections;
class GFG{
// Function to find a maximum product of
// a triplet in array of integers of size n
static int maxProduct(int []arr, int n)
{
// If size is less than 3, no triplet exists
if (n < 3)
return -1;
// Initialize Maximum, second maximum
// and third maximum element
int maxA = Int32.MinValue,
maxB = Int32.MinValue,
maxC = Int32.MinValue;
// Initialize Minimum and
// second minimum element
int minA = Int32.MaxValue,
minB = Int32.MaxValue;
for(int i = 0; i < n; i++)
{
// Update Maximum, second maximum
// and third maximum element
if (arr[i] > maxA)
{
maxC = maxB;
maxB = maxA;
maxA = arr[i];
}
// Update second maximum and
// third maximum element
else if (arr[i] > maxB)
{
maxC = maxB;
maxB = arr[i];
}
// Update third maximum element
else if (arr[i] > maxC)
maxC = arr[i];
// Update Minimum and second
// minimum element
if (arr[i] < minA)
{
minB = minA;
minA = arr[i];
}
// Update second minimum element
else if(arr[i] < minB)
minB = arr[i];
}
return Math.Max(minA * minB * maxA,
maxA * maxB * maxC);
}
// Driver code
public static void Main(string[] args)
{
int []arr = { 1, -4, 3, -6, 7, 0 };
int n = arr.Length;
int max = maxProduct(arr, n);
if (max == -1)
Console.Write("No Triplet Exists");
else
Console.Write("Maximum product is " + max);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// A O(n) javascript program to find maximum product
// pair in an array.
// Function to find a maximum product of
// a triplet in array of integers of size n
function maxProduct(arr , n)
{
// If size is less than 3, no triplet exists
if (n < 3)
return -1;
// Initialize Maximum, second maximum
// and third maximum element
var maxA = Number.MIN_VALUE,
maxB = Number.MIN_VALUE,
maxC = Number.MIN_VALUE;
// Initialize Minimum and
// second minimum element
var minA = Number.MAX_VALUE,
minB = Number.MAX_VALUE;
for(i = 0; i < n; i++)
{
// Update Maximum, second maximum
// and third maximum element
if (arr[i] > maxA)
{
maxC = maxB;
maxB = maxA;
maxA = arr[i];
}
// Update second maximum and
// third maximum element
else if (arr[i] > maxB)
{
maxC = maxB;
maxB = arr[i];
}
// Update third maximum element
else if (arr[i] > maxC)
maxC = arr[i];
// Update Minimum and second
// minimum element
if (arr[i] < minA)
{
minB = minA;
minA = arr[i];
}
// Update second minimum element
else if(arr[i] < minB)
minB = arr[i];
}
return Math.max(minA * minB * maxA,
maxA * maxB * maxC);
}
// Driver code
var arr = [ 1, -4, 3, -6, 7, 0 ];
var n = arr.length;
var max = maxProduct(arr, n);
if (max == -1)
document.write("No Triplet Exists");
else
document.write("Maximum product is " + max);
// This code is contributed by 29AjayKumar
</script>
Producción :
Maximum product is 168
Ejercicio:
1. Imprime la tripleta que tenga máximo producto.
2. Encuentra un producto mínimo de un triplete en una array.
Este artículo es una contribución de Aditya Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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