Dada una matriz de n elementos distintos. Encuentre el máximo del producto del mínimo de dos números en la matriz y la diferencia absoluta de sus posiciones, es decir, encuentre el valor máximo de abs(i - j) * min(arr[i] arr[j]) donde i y j varían de 0 a n-1.
algoritmo rr
Ejemplos:
Input : arr[] = {3 2 1 4} Output: 9 // arr[0] = 3 and arr[3] = 4 minimum of them is 3 and // absolute difference between their position is // abs(0-3) = 3. So product is 3*3 = 9 Input : arr[] = {8 1 9 4} Output: 16 // arr[0] = 8 and arr[2] = 9 minimum of them is 8 and // absolute difference between their position is // abs(0-2) = 2. So product is 8*2 = 16 Recommended Practice Encuentra el valor máximo ¡Pruébalo! A solución sencilla Para este problema es tomar cada elemento uno por uno y comparar este elemento con los elementos a su derecha. Luego calcule el producto del mínimo de ellos y la diferencia absoluta entre sus índices y maximice el resultado. La complejidad temporal de este enfoque es O (n^2).
Un solución eficiente para resolver el problema en complejidad de tiempo lineal. Tomamos dos iteradores. Izquierda=0 y Derecha=n-1 compare los elementos arr[Izquierda] y arr[derecha].
left = 0 right = n-1 maxProduct = -INF While (left < right) If arr[Left] < arr[right] currProduct = arr[Left]*(right-Left) Left++ . If arr[right] < arr[Left] currProduct = arr[Right]*(Right-Left) Right-- . maxProduct = max(maxProduct currProduct)
A continuación se muestra la implementación de la idea anterior.
C++// C++ implementation of code #include
// Java implementation of code import java.util.*; class GFG { // Function to calculate maximum value of // abs(i - j) * min(arr[i] arr[j]) in arr[] static int Maximum_Product(int arr[] int n) { // Initialize result int maxProduct = Integer.MIN_VALUE; // product of current pair int currProduct; // loop until they meet with each other int Left = 0 right = n - 1; while (Left < right) { if (arr[Left] < arr[right]) { currProduct = arr[Left] * (right - Left); Left++; } // arr[right] is smaller else { currProduct = arr[right] * (right - Left); right--; } // maximizing the product maxProduct = Math.max(maxProduct currProduct); } return maxProduct; } // Driver code public static void main(String[] args) { int arr[] = {8 1 9 4}; int n = arr.length; System.out.print(Maximum_Product(arr n)); } } // This code is contributed by Anant Agarwal.
# Python implementation of code # Function to calculate # maximum value of # abs(i - j) * min(arr[i] # arr[j]) in arr[] def Maximum_Product(arrn): # Initialize result maxProduct = -2147483648 # product of current pair currProduct=0 # loop until they meet with each other Left = 0 right = n-1 while (Left < right): if (arr[Left] < arr[right]): currProduct = arr[Left]*(right-Left) Left+=1 else: # arr[right] is smaller currProduct = arr[right]*(right-Left) right-=1 # maximizing the product maxProduct = max(maxProduct currProduct) return maxProduct # Driver code arr = [8 1 9 4] n = len(arr) print(Maximum_Product(arrn)) # This code is contributed # by Anant Agarwal.
// C# implementation of code using System; class GFG { // Function to calculate maximum // value of abs(i - j) * min(arr[i] // arr[j]) in arr[] static int Maximum_Product(int []arr int n) { // Initialize result int maxProduct = int.MinValue; // product of current pair int currProduct; // loop until they meet // with each other int Left = 0 right = n - 1; while (Left < right) { if (arr[Left] < arr[right]) { currProduct = arr[Left] * (right - Left); Left++; } // arr[right] is smaller else { currProduct = arr[right] * (right - Left); right--; } // maximizing the product maxProduct = Math.Max(maxProduct currProduct); } return maxProduct; } // Driver code public static void Main() { int []arr = {8 1 9 4}; int n = arr.Length; Console.Write(Maximum_Product(arr n)); } } // This code is contributed by nitin mittal.
// PHP implementation of code // Function to calculate // maximum value of // abs(i - j) * min(arr[i] // arr[j]) in arr[] function Maximum_Product($arr $n) { $INT_MIN = 0; // Initialize result $maxProduct = $INT_MIN; // product of current pair $currProduct; // loop until they meet // with each other $Left = 0; $right = $n - 1; while ($Left < $right) { if ($arr[$Left] < $arr[$right]) { $currProduct = $arr[$Left] * ($right - $Left); $Left++; } // arr[right] is smaller else { $currProduct = $arr[$right] * ($right - $Left); $right--; } // maximizing the product $maxProduct = max($maxProduct $currProduct); } return $maxProduct; } // Driver Code $arr = array(8 1 9 4); $n = sizeof($arr) / sizeof($arr[0]); echo Maximum_Product($arr $n); // This code is contributed // by nitin mittal. ?> <script> // Javascript implementation of code // Function to calculate // maximum value of // abs(i - j) * min(arr[i] // arr[j]) in arr[] function Maximum_Product(arr n) { let INT_MIN = 0; // Initialize result let maxProduct = INT_MIN; // Product of current pair let currProduct; // Loop until they meet // with each other let Left = 0 right = n - 1; while (Left < right) { if (arr[Left] < arr[right]) { currProduct = arr[Left] * (right - Left); Left++; } // arr[right] is smaller else { currProduct = arr[right] * (right - Left); right--; } // Maximizing the product maxProduct = Math.max(maxProduct currProduct); } return maxProduct; } // Driver Code let arr = new Array(8 1 9 4); let n = arr.length; document.write(Maximum_Product(arr n)); // This code is contributed by Saurabh Jaiswal </script>
Producción
16
Complejidad del tiempo: O (N log N) aquí N es la longitud de la matriz.
Complejidad espacial: O(1) ya que no se utiliza espacio adicional.
¿Cómo funciona esto?
Lo importante es mostrar que no perdemos ningún par potencial en el algoritmo lineal anterior, es decir, debemos demostrar que hacer izquierda++ o derecha no conduce a un caso en el que habríamos obtenido un valor más alto de maxProduct.
Tenga en cuenta que siempre multiplicamos por (derecha - izquierda).
- Si llega[izquierda]< arr[right] then smaller values of bien para la izquierda actual son inútiles ya que no pueden producir un valor más alto de maxProduct (porque multiplicamos con arr[left] con (right - left)). ¿Qué pasaría si arr[left] fuera mayor que cualquiera de los elementos en su lado izquierdo? En ese caso se debe haber encontrado un mejor par para ese elemento con el derecho actual. Por lo tanto, podemos aumentar la izquierda con seguridad sin perder ningún par mejor con la izquierda actual.
- Argumentos similares son aplicables cuando arr[right]< arr[left].