Genere una secuencia tal que la división flotante de los elementos de la array se maximice

Dada una array arr[] que consta de N enteros, la tarea es encontrar la expresión usando paréntesis ‘(‘ y ‘)’ y el operador de división ‘/’ para maximizar el valor de la expresión de la subsiguiente división flotante de los elementos de la array.

Ejemplos:

Entrada: arr[] = {1000, 100, 10, 2}
Salida: “1000/(100/10/2)”
Explicación:
El valor de la expresión 1000/(100/10/2) se puede calcular como 1000/ ((100/10)/2) = 200.

Entrada: arr[] = {2, 3, 4}
Salida: “2/(3/4)”

Enfoque: La idea se basa en la observación de que para cada división, el resultado es máximo solo cuando el denominador es mínimo. Por tanto, la tarea se reduce a colocar los paréntesis y los operadores de forma que el denominador sea mínimo. Considere el siguiente ejemplo para resolver el problema:

Considere una expresión 1000/100/10/2 .
Para que su valor sea máximo, el denominador debe minimizarse. Por lo tanto, los denominadores deben estar en la secuencia 100, 10, 2.
Ahora, considera los siguientes casos:

• 100 / (10 / 2) = (100 × 2) / 10 = 20
• (100 / 10) / 2 = 10 / 2 = 5

Por lo tanto, el valor minimizado de la expresión se obtiene para el segundo caso. Por lo tanto, 1000/(100/10/2) es la secuencia requerida.

Por lo tanto, a partir del ejemplo anterior, se puede concluir que el paréntesis debe colocarse en la secuencia después del primer entero que hace que toda la secuencia desde el segundo entero se reduzca al valor mínimo posible. 
Siga los pasos a continuación para resolver el problema:

• Inicialice una string S como «» para almacenar la expresión final.
• Si N es igual a 1 , imprima el entero en forma de string.
• De lo contrario, agregue arr[0] y “/(“ en S , y luego agregue todos los enteros restantes de arr[] separados por “/” .
• Por último, agregue «)» en la string S e imprima la string S como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to place the parenthesis
// such that the result is maximized
void generateSequence(int arr[], int n)
{
    // Store the required string
    string ans;
 
    // Add the first integer to string
    ans = to_string(arr[0]);
 
    // If the size of array is 1
    if (n == 1)
        cout << ans;
 
    // If the size of array is 2, print
    // the 1st integer followed by / operator
    // followed by the next integer
    else if (n == 2) {
        cout << ans + "/"
             << to_string(arr[1]);
    }
 
    // If size of array is exceeds two,
    // print 1st integer concatenated
    // with operators '/', '(' and next
    // integers with the operator '/'
    else {
        ans += "/(" + to_string(arr[1]);
 
        for (int i = 2; i < n; i++) {
            ans += "/" + to_string(arr[i]);
        }
 
        // Add parenthesis at the end
        ans += ")";
 
        // Print the final expression
        cout << ans;
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1000, 100, 10, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
    generateSequence(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG
{
 
// Function to place the parenthesis
// such that the result is maximized
static void generateSequence(int arr[], int n)
{
   
    // Store the required string
    String ans;
 
    // Add the first integer to string
    ans = Integer.toString(arr[0]);
 
    // If the size of array is 1
    if (n == 1)
        System.out.println(ans);
 
    // If the size of array is 2, print
    // the 1st integer followed by / operator
    // followed by the next integer
    else if (n == 2) {
        System.out.println(ans + "/"
            + Integer.toString(arr[1]));
    }
 
    // If size of array is exceeds two,
    // print 1st integer concatenated
    // with operators '/', '(' and next
    // integers with the operator '/'
    else {
        ans += "/(" + Integer.toString(arr[1]);
 
        for (int i = 2; i < n; i++) {
            ans += "/" + Integer.toString(arr[i]);
        }
 
        // Add parenthesis at the end
        ans += ")";
 
        // Print the final expression
        System.out.println(ans);
    }
}
 
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1000, 100, 10, 2 };
    int N = arr.length;
    generateSequence(arr, N);
}
}
 
// This code is contributed by code_hunt.

# Python3 program for the above approach
 
# Function to place the parenthesis
# such that the result is maximized
def generateSequence(arr, n):
     
    # Store the required string
    ans = ""
 
    # Add the first integer to string
    ans = str(arr[0])
 
    # If the size of array is 1
    if (n == 1):
        print(ans)
 
    # If the size of array is 2, print
    # the 1st integer followed by / operator
    # followed by the next integer
    elif (n == 2):
        print(ans + "/"+str(arr[1]))
     
    # If size of array is exceeds two,
    # pr1st integer concatenated
    # with operators '/', '(' and next
    # integers with the operator '/'
    else:
        ans += "/(" + str(arr[1])
 
        for i in range(2, n):
            ans += "/" + str(arr[i])
 
        # Add parenthesis at the end
        ans += ")"
 
        # Print final expression
        print(ans)
 
# Driver Code
if __name__ == '__main__':
    arr = [1000, 100, 10, 2]
    N = len(arr)
    generateSequence(arr, N)
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
class GFG
{
 
// Function to place the parenthesis
// such that the result is maximized
static void generateSequence(int []arr, int n)
{
   
    // Store the required string
    string ans="";
 
    // Add the first integer to string
    ans = arr[0].ToString();
 
    // If the size of array is 1
    if (n == 1)
        Console.WriteLine(ans);
 
    // If the size of array is 2, print
    // the 1st integer followed by / operator
    // followed by the next integer
    else if (n == 2) {
        Console.WriteLine(ans + "/"
            + arr[1].ToString());
    }
 
    // If size of array is exceeds two,
    // print 1st integer concatenated
    // with operators '/', '(' and next
    // integers with the operator '/'
    else {
        ans += "/(" + arr[1].ToString();
 
        for (int i = 2; i < n; i++) {
            ans += "/" + arr[i].ToString();
        }
 
        // Add parenthesis at the end
        ans += ")";
 
        // Print the final expression
        Console.WriteLine(ans);
    }
}
 
// Driver Code
public static void Main(string[] args)
{
    int []arr = { 1000, 100, 10, 2 };
    int N = arr.Length;
    generateSequence(arr, N);
}
}
 
// This code is contributed by chitranayal.

<script>
 
// Javascript program for the above approach
 
// Function to place the parenthesis
// such that the result is maximized
function generateSequence(arr, n)
{
    // Store the required string
    var ans;
 
    // Add the first integer to string
    ans = (arr[0].toString());
 
    // If the size of array is 1
    if (n == 1)
        document.write( ans);
 
    // If the size of array is 2, print
    // the 1st integer followed by / operator
    // followed by the next integer
    else if (n == 2) {
        document.write( ans + "/"
             + (arr[1].toString()));
    }
 
    // If size of array is exceeds two,
    // print 1st integer concatenated
    // with operators '/', '(' and next
    // integers with the operator '/'
    else {
        ans += "/(" + (arr[1].toString());
 
        for (var i = 2; i < n; i++) {
            ans += "/" + (arr[i].toString());
        }
 
        // Add parenthesis at the end
        ans += ")";
 
        // Print the final expression
        document.write( ans);
    }
}
 
// Driver Code
var arr = [1000, 100, 10, 2];
var N = arr.length;
generateSequence(arr, N);
 
// This code is contributed by noob2000.
</script>

1000/(100/10/2)

Complejidad temporal: O(N)
Espacio auxiliar: O(N)