Producto mínimo del elemento máximo y mínimo sobre todos los subarreglos posibles

Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el producto mínimo de máximo y mínimo entre todos los subarreglos posibles .

Ejemplos:

Entrada: arr[] = {6, 4, 5, 6, 2, 4}
Salida: 8
Explicación:
Considere el subarreglo {2, 4}, el producto del mínimo y el máximo para este subarreglo es 2*4 = 8, que es mínimo entre todos los subarreglos posibles.

Entrada: arr[] = {3, 1, 5, 2, 3, 2}
Salida: 3

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subarreglos posibles del arreglo y encontrar el producto del máximo y el mínimo de todos los subarreglos posibles . Después de verificar todos los subarreglos, imprima el mínimo de todos los productos obtenidos.

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la observación de que considerar el par de elementos adyacentes como un subarreglo porque incluir cualquier elemento del arreglo puede aumentar nuestro elemento máximo, lo que da como resultado el producto máximo.

Por lo tanto, la idea es encontrar el producto mínimo de todos los pares de elementos adyacentes para encontrar el producto mínimo resultante.

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 find the minimum product
//  of the minimum and maximum among all
//  the possible subarrays
int findMinMax(vector<int>& a)
{
 
    // Stores resultant minimum product
    int min_val = 1000000000;
 
    // Traverse the given array arr[]
    for (int i = 1; i < a.size(); ++i) {
 
        // Min of product of all two
        // pair of consecutive elements
        min_val = min(min_val, a[i] * a[i - 1]);
    }
   
    //  Return the resultant value
    return min_val;
}
 
//  Driver Code
int main()
{
    vector<int> arr = { 6, 4, 5, 6, 2, 4, 1 };
 
    cout << findMinMax(arr);
 
    return 0;
}
 
    // This code is contributed by rakeshsahni

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG
{
   
  //  Function to find the minimum product
  //  of the minimum and maximum among all
  //  the possible subarrays
  static int findMinMax(int[] a)
  {
 
    // Stores resultant minimum product
    int min_val = 1000000000;
 
    // Traverse the given array arr[]
    for (int i = 1; i < a.length; ++i) {
 
      // Min of product of all two
      // pair of consecutive elements
      min_val = Math.min(min_val, a[i] * a[i - 1]);
    }
 
    //  Return the resultant value
    return min_val;
  }
 
  //  Driver Code
  public static void main (String[] args)
  {
    int[] arr = { 6, 4, 5, 6, 2, 4, 1 };
 
    System.out.println(findMinMax(arr));
  }
}
 
// This code is contributed by maddler.

# Python program for the above approach
 
# Function to find the minimum product
# of the minimum and maximum among all
# the possible subarrays
def findMinMax(a):
 
    # Stores resultant minimum product
    min_val = 1000000000
 
       # Traverse the given array arr[]
    for i in range(1, len(a)):
 
        # Min of product of all two
        # pair of consecutive elements
        min_val = min(min_val, a[i]*a[i-1])
 
    # Return the resultant value
    return min_val
 
 
# Driver Code
if __name__ == ("__main__"):
 
    arr = [6, 4, 5, 6, 2, 4, 1]
 
    print(findMinMax(arr))

// C# program for the above approach
using System;
 
public class GFG
{
 
  //  Function to find the minimum product
  //  of the minimum and maximum among all
  //  the possible subarrays
  static int findMinMax(int[] a)
  {
  
    // Stores resultant minimum product
    int min_val = 1000000000;
  
    // Traverse the given array arr[]
    for (int i = 1; i < a.Length; ++i) {
  
      // Min of product of all two
      // pair of consecutive elements
      min_val = Math.Min(min_val, a[i] * a[i - 1]);
    }
  
    //  Return the resultant value
    return min_val;
  }   
   
    // Driver Code
    public static void Main (string[] args)
    {
        int[] arr = { 6, 4, 5, 6, 2, 4, 1 };
  
        Console.WriteLine(findMinMax(arr));
    }
}
 
// This code is contributed by avijitmondal1998.

   <script>
        // JavaScript Program to implement
        // the above approach
 
//  Function to find the minimum product
//  of the minimum and maximum among all
//  the possible subarrays
function findMinMax( a)
{
 
    // Stores resultant minimum product
    let min_val = 1000000000;
 
    // Traverse the given array arr[]
    for (let i = 1; i < a.length; ++i) {
 
        // Min of product of all two
        // pair of consecutive elements
        min_val = Math.min(min_val, a[i] * a[i - 1]);
    }
   
    //  Return the resultant value
    return min_val;
}
 
//  Driver Code
 
    let arr = [6, 4, 5, 6, 2, 4, 1];
    document.write( findMinMax(arr))
 
// This code is contributed by Potta Lokesh
    </script>

4

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