El producto de triplete más grande en una corriente

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í. 

1. Insertar arr[i] en la cola de prioridad
2. 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.
3. Imprimir x*y*z
4. Vuelva a insertar x, y, z.

Implementación:

// 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 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 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# 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

<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>

-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.