Subarreglo contiguo de relación más grande

Dada una array arr[] de N números, la tarea es encontrar la proporción más grande de subarreglo contiguo de la array dada. 

Ejemplos: 

Entrada: arr = { -1, 10, 0.1, -8, -2 }
Salida: 100 
Explicación:
El subarreglo {10, 0.1} da 10 / 0.1 = 100 que es la relación más grande.

Entrada: arr = { 2, 2, 4, -0.2, -1 }
Salida: 20
Explicación:
El subarreglo {4, -0.2, -1} tiene la relación más grande como 20.

 

Enfoque: La idea es generar todos los subarreglos del arreglo y para cada subarreglo, encontrar la razón del subarreglo como arr[i] / arr[i+1] / arr[i+2] y así sucesivamente. Lleve un registro de la relación máxima y devuélvala al final.
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return maximum
// of two double values
double maximum(double a, double b)
{
    // Check if a is greater
    // than b then return a
    if (a > b)
        return a;
 
    return b;
}
 
// Function that returns the
// Ratio of max Ratio subarray
double maxSubarrayRatio(
  double arr[], int n)
{
   
    // Variable to store
    // the maximum ratio
    double maxRatio = INT_MIN;
 
    // Compute the product while
    // traversing for subarrays
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
           
            double ratio = arr[i];
           
            for (int k = i + 1; k <= j; k++) {
               
                // Calculate the ratio
                ratio = ratio / arr[k];
            }
           
            // Update max ratio
            maxRatio = maximum(maxRatio, ratio);
        }
    }
 
    // Print the answer
    return maxRatio;
}
 
// Driver code
int main()
{
    double arr[] = { 2, 2, 4, -0.2, -1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxSubarrayRatio(arr, n);
    return 0;
}

Java

// Java program for the above approach
class GFG{
     
// Function to return maximum
// of two double values
static double maximum(double a, double b)
{
     
    // Check if a is greater
    // than b then return a
    if (a > b)
        return a;
 
    return b;
}
 
// Function that returns the
// Ratio of max Ratio subarray
static double maxSubarrayRatio(double arr[],
                               int n)
{
     
    // Variable to store
    // the maximum ratio
    double maxRatio = Integer.MIN_VALUE;
 
    // Compute the product while
    // traversing for subarrays
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            double ratio = arr[i];
             
            for(int k = i + 1; k <= j; k++)
            {
                 
                // Calculate the ratio
                ratio = ratio / arr[k];
            }
             
            // Update max ratio
            maxRatio = maximum(maxRatio, ratio);
        }
    }
 
    // Print the answer
    return maxRatio;
}
     
// Driver code   
public static void main(String[] args)
{
    double arr[] = { 2, 2, 4, -0.2, -1 };
    int n = arr.length;
     
    System.out.println(maxSubarrayRatio(arr, n));
}
}
 
// This code is contributed by rutvik_56

Python3

# Python3 program for the above approach
import sys
 
# Function to return maximum
# of two double values
def maximum(a, b):
 
    # Check if a is greater
    # than b then return a
    if (a > b):
        return a
 
    return b
 
# Function that returns the
# Ratio of max Ratio subarray
def maxSubarrayRatio(arr, n):
 
    # Variable to store
    # the maximum ratio
    maxRatio = -sys.maxsize - 1
 
    # Compute the product while
    # traversing for subarrays
    for i in range(n):
        for j in range(i, n):
            ratio = arr[i]
         
            for k in range(i + 1, j + 1):
             
                # Calculate the ratio
                ratio = ratio // arr[k]
         
            # Update max ratio
            maxRatio = maximum(maxRatio, ratio)
         
    # Print the answer
    return int(maxRatio)
 
# Driver code
if __name__ == "__main__":
     
    arr = [ 2, 2, 4, -0.2, -1 ]
    n = len(arr)
     
    print(maxSubarrayRatio(arr, n))
 
# This code is contributed by chitranayal

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to return maximum
// of two double values
static double maximum(double a, double b)
{
     
    // Check if a is greater
    // than b then return a
    if (a > b)
        return a;
 
    return b;
}
 
// Function that returns the
// Ratio of max Ratio subarray
static double maxSubarrayRatio(double []arr,
                               int n)
{
     
    // Variable to store
    // the maximum ratio
    double maxRatio = int.MinValue;
 
    // Compute the product while
    // traversing for subarrays
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            double ratio = arr[i];
             
            for(int k = i + 1; k <= j; k++)
            {
                 
                // Calculate the ratio
                ratio = ratio / arr[k];
            }
             
            // Update max ratio
            maxRatio = maximum(maxRatio, ratio);
        }
    }
 
    // Print the answer
    return maxRatio;
}
     
// Driver code
public static void Main(String[] args)
{
    double []arr = { 2, 2, 4, -0.2, -1 };
    int n = arr.Length;
     
    Console.WriteLine(maxSubarrayRatio(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to return maximum
// of two double values
function maximum(a, b)
{
 
    // Check if a is greater
    // than b then return a
    if (a > b)
        return a;
 
    return b;
}
 
// Function that returns the
// Ratio of max Ratio subarray
function maxSubarrayRatio(arr, n)
{
   
    // Variable to store
    // the maximum ratio
    var maxRatio = -1000000000;
 
    // Compute the product while
    // traversing for subarrays
    for (var i = 0; i < n; i++)
    {
        for (var j = i; j < n; j++)
        {
           
            var ratio = arr[i]; 
            for (var k = i + 1; k <= j; k++)
            {
               
                // Calculate the ratio
                ratio = ratio / arr[k];
            }
           
            // Update max ratio
            maxRatio = maximum(maxRatio, ratio);
        }
    }
 
    // Print the answer
    return maxRatio;
}
 
// Driver code
var arr = [ 2, 2, 4, -0.2, -1 ];
var n = arr.length;
document.write( maxSubarrayRatio(arr, n));
 
// This code is contributed by rrrtnx.
</script>
Producción

20

Complejidad Temporal: (N 3 )
Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *