Dado un flujo de enteros representado como arr[]. Para cada índice i de 0 a n-1, imprima la multiplicación del elemento más grande, el segundo más grande y el tercero más grande del subarreglo arr[0…i]. Si i < 2 imprime -1.
Ejemplos:
Input : arr[] = {1, 2, 3, 4, 5}
Output :-1
-1
6
24
60
Explanation : for i = 2 only three elements
are there {1, 2, 3} so answer is 6. For i = 3
largest three elements are {2, 3, 4} their
product is 2*3*4 = 24 ....so on
Usaremos la cola de prioridad aquí.
- Insertar arr[i] en la cola de prioridad
- Como el elemento superior en la cola de prioridad es el más grande, sáquelo y guárdelo como x. Ahora, el elemento superior en la cola de prioridad será el segundo elemento más grande en el subarreglo arr[0…i], extráigalo y guárdelo como y. Ahora el elemento superior es el tercer elemento más grande en el subarreglo arr[0…i], así que sáquelo y guárdelo como z.
- Imprimir x*y*z
- Vuelva a insertar x, y, z.
Implementación:
C++
// C++ implementation of largest triplet
// multiplication
#include <bits/stdc++.h>
using namespace std;
// Prints the product of three largest numbers
// in subarray arr[0..i]
void LargestTripletMultiplication(int arr[], int n)
{
// call a priority queue
priority_queue<int> q;
// traversing the array
for (int i = 0; i < n; i++) {
// pushing arr[i] in the array
q.push(arr[i]);
// if less than three elements are present
// in array print -1
if (q.size() < 3)
cout << "-1" << endl;
else {
// pop three largest elements
int x = q.top();
q.pop();
int y = q.top();
q.pop();
int z = q.top();
q.pop();
// Reinsert x, y, z in priority_queue
int ans = x * y * z;
cout << ans << endl;
q.push(x);
q.push(y);
q.push(z);
}
}
return;
}
// Driver Function
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
LargestTripletMultiplication(arr, n);
return 0;
}
Java
// Java implementation of largest triplet
// multiplication
import java.util.Collections;
import java.util.PriorityQueue;
class GFG {
// Prints the product of three largest numbers
// in subarray arr[0..i]
static void LargestTripletMultiplication(int arr[], int n)
{
// call a priority queue
PriorityQueue<Integer> q = new PriorityQueue(Collections.reverseOrder());
// traversing the array
for (int i = 0; i < n; i++) {
// pushing arr[i] in array
q.add(arr[i]);
// if less than three elements are present
// in array print -1
if (q.size() < 3)
System.out.println("-1");
else {
// pop three largest elements
int x = q.poll();
int y = q.poll();
int z = q.poll();
// Reinsert x, y, z in priority_queue
int ans = x * y * z;
System.out.println(ans);
q.add(x);
q.add(y);
q.add(z);
}
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
LargestTripletMultiplication(arr, n);
}
}
// This code is contributed by shubham96301
Python3
# Python3 implementation of largest triplet # multiplication from queue import PriorityQueue # Prints the product of three largest # numbers in subarray arr[0..i] def LargestTripletMultiplication(arr, n): # Call a priority queue q = PriorityQueue() # Traversing the array for i in range(n): # Pushing -arr[i] in array # to get max PriorityQueue q.put(-arr[i]) # If less than three elements # are present in array print -1 if (q.qsize() < 3): print(-1) else: # pop three largest elements x = q.get() y = q.get() z = q.get() # Reinsert x, y, z in # priority_queue ans = x * y * z print(-ans) q.put(x); q.put(y); q.put(z); # Driver Code if __name__ == '__main__': arr = [ 1, 2, 3, 4, 5 ] n = len(arr) LargestTripletMultiplication(arr, n) # This code is contributed by math_lover
C#
// C# implementation of largest triplet
// multiplication
using System;
using System.Collections.Generic;
public class GFG {
// Prints the product of three largest numbers
// in subarray arr[0..i]
static void LargestTripletMultiplication(int []arr, int n)
{
// call a priority queue
List<int> q = new List<int>();
// traversing the array
for (int i = 0; i < n; i++)
{
// pushing arr[i] in array
q.Add(arr[i]);
q.Sort();
q.Reverse();
// if less than three elements are present
// in array print -1
if (q.Count < 3)
Console.WriteLine("-1");
else
{
// pop three largest elements
int x = q[0];
int y = q[1];
int z = q[2];
q.RemoveRange(0, 3);
// Reinsert x, y, z in priority_queue
int ans = x * y * z;
Console.WriteLine(ans);
q.Add(x);
q.Add(y);
q.Add(z);
}
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 5 };
int n = arr.Length;
LargestTripletMultiplication(arr, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript implementation of largest triplet
// multiplication
// Prints the product of three largest numbers
// in subarray arr[0..i]
function LargestTripletMultiplication(arr , n) {
// call a priority queue
var q = [];
// traversing the array
for (i = 0; i < n; i++) {
// pushing arr[i] in array
q.push(arr[i]);
q.sort();
// if less than three elements are present
// in array print -1
if (q.length < 3)
document.write("-1<br/>");
else {
// pop three largest elements
q.sort();
var x = q.pop();
var y = q.pop();
var z = q.pop();
// Reinsert x, y, z in priority_queue
var ans = x * y * z;
document.write(ans+"<br/>");
q.push(x);
q.push(y);
q.push(z);
q.sort();
q.reverse();
}
}
}
// Driver code
var arr = [ 1, 2, 3, 4, 5 ];
var n = arr.length;
LargestTripletMultiplication(arr, n);
// This code contributed by umadevi9616
</script>
Producción
-1 -1 6 24 60
Este artículo es una contribución de Ayush Jha . 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