Maximiza el resultado de la división de Array usando operaciones dadas

Dada una array arr[] de N enteros, la tarea es encontrar el valor máximo posible que queda en la array repitiendo los siguientes dos pasos: 

• Elimina dos elementos cualquiera de la array.
• Inserta el cociente de su división en la array.

Nota: Se nos permite cambiar el orden de los elementos.

Ejemplos: 

Entrada: arr[] = {100, 1000, 10, 2} 
Salida: 200 
Explicación: 

• Retire 100 y 10 de la array. Inserte 10 (= 100/10) nuevamente en la array.
• Retire 10 y 2 de la array. Inserta 5 en la array.
• Retire 1000 y 5 de la array. Inserte 200 en la array

Por lo tanto, el resultado máximo es 200.

Entrada: arr[] = {2, 100, 1} 
Salida: 50 

Planteamiento: 
Para resolver el problema mencionado anteriormente, podemos observar que obtendremos el máximo resultado cuando los elementos se ordenen en orden decreciente y las operaciones de división ocurran en la secuencia arr[0] / ( arr[1] / arr[2] / arr[3]…..arr[n-1]) de la array ordenada inversamente. Por lo tanto, ordene la array en consecuencia y calcule el resultado apropiado. 

El siguiente código es la implementación del enfoque anterior:  

// C++ implementation to maximize the
// result of division of the given
// array elements
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the max result
float maxDivision(int arr[], int n)
{
 
    // Sort the array in descending order
    sort(arr, arr + n, greater<int>());
 
    float mxdiv = arr[1];
 
    // loop to divide in this order
    // arr[0] / ( arr[1] / arr[2] / ....
    // arr[n-2] / arr[n-1])
    for (int i = 2; i < n; ++i)
        mxdiv = mxdiv / arr[i];
 
    // return the final result
    return arr[0] / mxdiv;
}
 
// Driver code
int main()
{
 
    int arr[] = { 100, 1000, 10, 2 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << maxDivision(arr, n);
 
    return 0;
}

// Java implementation to maximize the
// result of division of the given
// array elements
import java.util.*;
 
class GFG{
 
// Function to find the max result
static float maxDivision(Integer arr[], int n)
{
 
    // Sort the array in descending order
    Arrays.sort(arr, Collections.reverseOrder());
 
    float mxdiv = arr[1];
 
    // Loop to divide in this order
    // arr[0] / ( arr[1] / arr[2] / ....
    // arr[n-2] / arr[n-1])
    for(int i = 2; i < n; ++i)
       mxdiv = mxdiv / arr[i];
 
    // Return the final result
    return arr[0] / mxdiv;
}
 
// Driver code
public static void main(String[] args)
{
 
    Integer arr[] = { 100, 1000, 10, 2 };
    int n = arr.length;
 
    System.out.print((int)maxDivision(arr, n));
}
}
 
// This code is contributed by amal kumar choubey

# Python3 implementation to maximize
# the result of division of the
# given array elements
 
# Function to find the max result
def maxDivision(arr, n):
     
    # Sort the array in descending order
    arr.sort(reverse = True)
    mxdiv = arr[1]
     
    # Loop to divide in this order
    # arr[0] / ( arr[1] / arr[2] / ....
    # arr[n-2] / arr[n-1])
    for i in range(2, n):
        mxdiv = mxdiv / arr[i]
         
    # Return the final result
    return arr[0] / mxdiv
 
# Driver code
arr = [ 100, 1000, 10, 2 ]
n = len(arr)
 
print(maxDivision(arr, n))
 
# This code is contributed by ishayadav181

// C# implementation to maximize the
// result of division of the given
// array elements
using System;
 
class GFG{
 
// Function to find the max result
static float maxDivision(int []arr, int n)
{
 
    // Sort the array in descending order
    Array.Sort(arr);
    Array.Reverse(arr);
 
    float mxdiv = arr[1];
 
    // Loop to divide in this order
    // arr[0] / ( arr[1] / arr[2] / ....
    // arr[n-2] / arr[n-1])
    for(int i = 2; i < n; ++i)
       mxdiv = mxdiv / arr[i];
 
    // Return the readonly result
    return arr[0] / mxdiv;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 100, 1000, 10, 2 };
    int n = arr.Length;
 
    Console.Write((int)maxDivision(arr, n));
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript implementation to maximize
// the result of division of the given
// array elements
 
// Function to find the max result
function maxDivision(arr, n)
{
     
    // Sort the array in descending order
    arr.sort((a, b) => b - a);
   
    let mxdiv = arr[1];
   
    // Loop to divide in this order
    // arr[0] / ( arr[1] / arr[2] / ....
    // arr[n-2] / arr[n-1])
    for(let i = 2; i < n; ++i)
        mxdiv = mxdiv / arr[i];
   
    // Return the final result
    return arr[0] / mxdiv;
}
  
// Driver Code
let arr = [ 100, 1000, 10, 2 ];
let n = arr.length;
 
document.write(maxDivision(arr, n));
 
// This code is contributed by susmitakundugoaldanga
 
</script>

200

Complejidad de tiempo: O(N logN)